데옴's 기록장

k개의 소수들의 곱을 순서대로 나열할 때, n번째로 오는 숫자를 구하는 문제이다. 가장 단순하게 k개의 소수들로 만들 수 있는 숫자들을 만든다는 전략을 사용해 보자. i번째로 오는 수에 k개의 소수를 각각 곱하여 만들 수 있는 수를 우선순위큐에 넣어준다. 중복되는 경우가 있을 수 있기 때문에 하나의 경우만 있을 수 있도록 처리해 준다. 문제의 메모리가 적으므로 메모리 초과에 유의하자. 더보기 #define _CRT_SECURE_NO_WARNING #include #include #include #include using namespace std; using namespace __gnu_cxx; // utils #define fastio ios::sync_with_stdio(false);cin.tie(0)..

체감으로는 골드 4?정도로 느껴지는 우선순위큐를 잘 활용하는 법을 안다면 쉽게 구현할 수 있는 문제라고 생각한다. 문제를 꼼꼼히 읽으면 쉽게 접근법을 찾아낼 수 있다. 우선 요구사항을 정리하면 다음과 같다. 1. 계산대에 줄을 선 순서대로 고객이 들어온다. 2. 빨리 계산이 끝나는 계산대에 고객을 안내하고, 기다려야 하는 시간이 같다면 계산대 번호가 작은 순서대로 고객을 안내한다. 3. 계산이 끝나는 대로 고객이 나간다. 계산을 마친 고객이 여러 명이라면 계산대 번호가 큰 순서대로 나간다. 기본적으로 계산대에 사람이 있어야 하므로 처음 $min(k, n)$명에게 순서대로 계산대에 배정한다. 이제 계산이 가장 빨리 끝나는 계산대의 시간을 $t$라고 해보자, 다음 손님이 왔을 때 그 계산대에서 계산을 끝마치..

문제 제목이 참... 좀 그렇다 ㅋㅋ 이 문제는 BOJ 1489와 같다. 솔직히 이게 왜 플레지.. 생각이 들 정도로 단순한 그리디로 해결된다는 사실이다. 구해야 하는 것은 이안이와 예환이가 점수내기를 하고 이안이가 얻을 수 있는 최대 이익이다. 비교하기 쉽게 일단 정렬을 해보자. 이안이가 가장 최적의 효율로 내기에서 이기기 위해선 점수차가 최소가 되면서 이기거나 비기는 것이 중요하다. 여기까지 느낌을 잡았다면 그 후는 구현만 하면 된다. n제한은 10000으로 $O(n^2)$ 알고리즘을 사용할 수 있다. 이안이가 최소한의 점수차로 이길 수 있는 모든 과목 -> 무승부가 가능한 모든 과목 -> 지는 모든 과목순으로 점수를 계산해 주면 된다. 더보기 struct team { int point; bool u..

면접을 보고 난 후 2일이 지났다. 드디어 11/13일, 5시에 합격 발표가 나온다니 그 전날부터 면접 보는 것과 같은 긴장감을 가질 수 있었다. 11/13일로 만들기 위해 잠을 청했고 침대에 누워 눈을 감으니 불합격의 메시지가 담긴 입학관리 시스템의 모습이 보였다.. 꿈을 꾸는데도 자꾸만 불합격의 예감이 들었다. 면접 때 제대로 답하지 못한 찝찝함 때문이었을까? 점점 불안한 마음에 잠에 제대로 들지 못한 채 날이 밝았다. 학교에 등교하고 디미고에 지원한 친구와 함께 손을 붙잡고 붙기를 간절히 바라였다. 발표 전까지 우리는 1분마다 디미고 합격 기원을 외치기로 하였고 실행했다(?) 점점 면접 때 어떤 말실수를 했고 과연 면접관이 원했던 말이 무엇이었는지 의문이 들기 시작했다. 이런 생각을 가지게 되면서 ..

혼자 사다리타기에 대한 다양한 방법으로 연구하며 시간을 보내다 만난 문제이다. 오랜 시간 연구했던 탓인지 상대적으로 쉽게 해결할 수 있었다. 사다리들이 배치되어 있고 꼭 필요한 사다리들만 출력하는 문제이다. 문제를 해결하기 앞서 사다리타기의 성질을 알아보자. 세로줄 사이에 사다리를 하나 놓으면 a,b는 서로 swap이 된다. 그렇다면 여기서 할 수 있는 발상은 매우 단순하다. 한번 이미 사다리를 타고 이동했을때의 모든 도착지점을 안다고 생각해보자. i번째 출발점에서 도착점으로 가기 위해서는 그 거리만큼 사다리가 필요하다. 여기서 중복되는 사다리들이 존재할 수 있는데 여기서는 교차점이라고 말하겠다. n개의 출발점에서 도착지점으로 이동하는 모습을 표현하면 결국 사다리는 중복됨으로 교차점이 발생하는 구간에서 ..

2023/11/11, 빼빼로 데이에 디미고 면접을 보러 갔다. 평소 열심히 학교 생활을 하며 성적도 잘 나왔고 자소서도 열심히 작성해서 1차는 무난하게 붙었다. 문제는 2차 면접이었고 그게 빼빼로 데이인 오늘이었다. 가기 전까지는 ps를 하며 매우 즐거운 시간을 보냈지만 막상 도착하고 보니 굉장히 떨렸다..(어쩌면 당연한 것일지도) 대기실에 입실하고 많은 디미고 형님누님들이 디미고에 대한 환상(?)을 깨주기도 하고 재밌는 썰도 많이 풀어주셨다. 디미고 기숙사 생활을 하며 제일 재밌는 게 샤워시간이라나 뭐라나... 아무튼 나는 대기번호 6번이었고 같이 디미고에 지원한 친구는 3번으로 먼저 면접을 보러 갔다. 친구가 면접을 보러 나가고 인싸의 향기가 나는 디미고 선배 중 한 명은 노래를 부르는 장기자랑을 했..

유명한 그리디의 스케줄링 문제이다. 발상이 떠오르지 않는다면 어려울 수 있는 그리디 문제이다. 그러나 한번 알아두면 평생 쓴다! 어떤 방법으로 강의들을 배정해야 최소한으로 필요한 강의실을 개수를 구할 수 있을까? 순서대로 계획을 짜보자 1. 빨리 시작하는 순으로 배정한다. 시작이 빠른 강의가 가장 늦게 끝나는 경우가 있음으로 사용하기 어렵다. 2. 강의 시간이 짧은 순서대로 배정한다. 강의 시간이 짧은 강의가 제일 나중에 나오게 되면 비효율적이다. 3. 적게 겹치는 강의부터 배정한다. 이 역시 쉽게 반례를 찾을 수 있다. 4. 빨리 끝나는 순으로 배정한다. 뭔 짓을 해도 반례를 찾을 수 없다. 전략이 나왔다. 빨리 끝나는 순으로 강의를 배정시켜 보자. 이는 우선순위큐를 이용해 배정할 수 있다. 빠른 순으..

레이지 세그를 공부하던 중 만난 문제다.. 그냥 딱 보면 이게 뭐지 싶은 발상이 쉽지 않았다. 문제에는 2가지 쿼리가 주어진다. 1 l r : $\sum_{i=l}^{r}A_i+i-l+1$ 을 한다. 2 x : $A_i$ 의 값을 출력한다. 문제에서 1번 쿼리를 하면 $\sum_{i=l}^{r}A_i+i-l+1$을 하기 때문에 일반적인 구간 합 구하기 방법으로는 찾기 힘들다. 그렇다면 어떤 방법을 사용해야 될까에 대해 고민해 봐야 되는데 여기서 누적합을 응용하면 문제가 단순하게 변한다. 여기 예제 1번을 보자 1 2 1 2 1 여기서 누적합은 앞에 저장된 수를 더하지만 이번엔 앞에 수로 빼보자 1 1 -1 1 -1 이 상태에서 누적합을 하면 다시 처음 상태로 복원되는 것을 확인할 수 있다. 그럼 이걸 가..

체감 난이도: D5 태그: 그리디, 정렬, 우선순위 큐 문제 요약: 최소 개수의 강의실을 사용해 모든 강의를 진행하게 한다. (단 1번 강의와 2번 강의는 같은 강의실에 배정하면 안 된다.) 강의실 배정의 상위 버전 문제이다. 우선 평범하게 강의실 배정을 하는 로직을 기반으로 생각 해보자. 만약 가장 빨리 끝나는 강의실에 1번 또는 2번 강의가 있는데 2번 또는 1번 강의가 들어온다면 다음으로 빨리 끝나는 강의실에 배정하는 식으로 진행시켜보자. 아래와 같은 상황이 들어오면 어떨까? 더보기 7 1 2 6 8 1 2 2 4 3 5 4 6 5 7 강의실 배정을 조금 변형한 방법으로는 이 상황을 해결할 수 없다. 위 상황을 조금 보기 쉽게 정렬해보면 아래와 같다. 더보기 1 2 (1) 1 2 (3) 2 4 (4..

사실 이 문제를 풀때 1624번을 푼다는 전제 하에 풀어보았지만... 1624는 다른 접근 방식으로 풀었다.. 이 문제는 생각보다 단순한 발상을 가지고 풀 수 있었다. 우선 최소한의 덱을 생성해 수열을 정렬된 상태로 만드는 것이 목표이다. 그렇다면 한가지를 떠올려볼 수 있다. 이미 정렬된 상태의 수열과 비교를 하며 덱에 추가할지 말지를 판별해볼 수 있지 않을까? 순서대로 덱에 집어넣어보며 정렬된 수열과 확인하는 방법으로 이 문제를 해결 할 수 있다. 처음에 무조건 덱이 하나 이상 있어야 함으로 덱에는 첫 번째 수가 있고 나머지를 순서대로 넣을지 말지를 정해본다. 현재 만들어진 모든 덱을 전부 둘러보며 j번째 덱에서 front와 back의 인덱스값과 i번째 수의 인덱스 값이 1차이가 난다면 인접한 수임을 ..