백준/구간 쿼리 (3) 썸네일형 리스트형 백준 12986 - 화려한 마을 2 https://www.acmicpc.net/problem/12986 $O((N+Q)\sqrt N \log N)$ 솔루션 - Mo's + Indexed heap Mo's 알고리즘 적용을 위해 쿼리를 정렬한다. 그리고 -100000부터 100000까지의 값을 index로 취급하면 가장 많이 출연한 원소의 횟수를 indexed heap로 찾을 수 있다. 그러면 각 쿼리를 처리하면서 원소의 출연 횟수를 구역을 횡단할 때마다 $O(\log N)$의 시간 복잡도로 갱신하게 되고 쿼리의 답은 max indexed heap의 top이 된다. 시간 복잡도 : $O((N+Q)\sqrt N \log N)$ 전체 코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22.. 백준 2912 - 백설공주와 난쟁이 https://www.acmicpc.net/problem/2912 필요 지식 이 포스트에서는 머지 소트 트리를 사용하며 약간의 수학적 통찰력이 필요하다. 모스 알고리즘 같은 다른 풀이는 다루지 않는다. 아이디어 A번째 난쟁이와 B번째 난쟁이까지를 하나의 구간으로 보자. 그러면 이 구간에서 절반을 초과하는 색깔(이하 과반수)이 존재하는지 구해야 한다. 구간에서 어떤 원소 하나를 선택한다고 해보자. 이 색깔이 과반수일 확률은 $\frac{1 + \epsilon}{2}$이라는 것은 바로 이해할 수 있다. 반대로 과반수가 아닐 확률은 $\frac{1 - \epsilon}{2}$가 된다는 뜻이다. 그러면 원소를 r번 선택했을 때 과반수가 아닐 확률은 $(\frac{1 - \epsilon}{2})^{r}$가 된다... 백준 13548 - 수열과 쿼리 6 https://www.acmicpc.net/problem/13548 모스 알고리즘의 연습 문제 중 하나이다. $O((N + M) \sqrt M)$으로 처리를 하되, 다음을 이용해야 한다. 포인터가 한 index 움질일 때마다 구간에 속한 수의 출현 빈도의 변화량 d는 $-1 \leq d \leq 1$ 이므로 $O(1)$에 출현 횟수의 변화를 계산할 수 있다. 이를 구현하기 위해 어떤 수를 index로 하여 그 출현 횟수를 저장하는 배열 mp와 어떤 출현 횟수를 index로 하여 그 출현 횟수의 횟수를 저장하는 배열 counter를 둔다. 이렇게 되면 구간이 1씩 길어질 때마다 새로 포함된 값 x를 mp에 반영하기 전에 기존 구간에서 x의 출현 횟수를 저장한 counter를 바꿔줘야 한다. counter의.. 이전 1 다음
