평방 분할 (Sqrt Decompositon) : 루트로 쪼개보자.
세그먼트 트리를 모를 때, k번째로 빠른 수를 어떻게 찾아야 할 지 모를 때, 어떤 방법을 쓰면 좋을까요? n이 적당히 크다면, 우리는 이런 아이디어를 생각해 볼 수 있습니다. 구간이 n개가 아닌 sqrt(n)개. 그리고, 구간 별 원소 갯수도 sqrt(n)개. 사실, 이것을 응용한 알고리즘이 Mo's algorithm인데, 여기까지 다루지는 않겠습니다. 예를 들어, 배열의 임의의 원소가 구간 [1,9]에 속하는 자연수라고 해 봅시다. 이 때 배열 [1, 3, 3, 4, 4, 5, 5, 6, 7, 7, 7, 8, 8, 9]에서, 13번째로 작은 수를 찾기 위해서 어떻게 하면 좋을까요? 일단, co[x]는 x가 나타나는 빈도수를 나타낸 겁니다. 그러면 단순하게 생각하면, 누적 값을 더해가면서, 1이 출현하..
자료알고/자료구조
2019. 9. 22. 00:18
최근댓글