HilbertMO : alternative query sorting for Mo's algorithm

2018. 11. 15. 16:03CS 이론/알고리즘

원본 Codeforces 블로그


문제를 잘 푸는 사람일수록 알고리즘을 암기하기보단 끊임없이 고찰하고, 최적화하고, 예외를 효과적으로 비껴가는 방법을 연구하는 것 같다. 그런 의미에서 이 포스팅 작성자도 굉장히 존경스럽다. 세상은 넓고 갓갓은 많아..


MO's algorithm


흔히 루트질로 불리는 MO's algorithm은 배열에 대한 구간 쿼리를 오프라인으로 처리하는 많은 문제를 아슬아슬한 복잡도로 해결할 수 있게 해주는 트릭이다.


kesakiyo님의 친절한 introduction


끄흐수님의 깔끔한 introduction


MO's algorithm으로 문제를 풀기 위해서는 다음이 성립해야 한다 : 

- 구간 [s, e]에 대한 쿼리의 답을 알고 있다면, 구간 [s-1, e] 또는 [s, e+1]에 대한 답을 빠르게 알 수 있다. (push)

- 구간 [s, e]에 대한 쿼리의 답을 알고 있다면, 구간 [s+1, e] 또는 [s, e-1]에 대한 답을 빠르게 알 수 있다. (pop)

: push / pop을 쿼리 옮기기라고 하자.


저 조건이 주어졌을 때 바로 떠오르는 Naive한 알고리즘이 있다.

- 쿼리를 아무 생각 없이 죽 늘어놓고, \(i\)번째 쿼리 \([s_{i}, e_{i}]\)에서 \(i+1\)번째 쿼리 \([s_{i+1}, e_{i+1}]\)로 넘어갈 때 쿼리 옮기기를 \(|s_{i} - s_{i+1}| + |e_{i} - e_{i+1}|\) 번 사용해서 넘어간다.


하지만 이 알고리즘은 \((s_{2i}, e_{2i}) = (1,1)\), \((s_{2i-1}, e_{2i-1}) = (n, n)\)으로 주어질 경우 쿼리 옮기기에 \(\Theta (N)\)의 시간이 소모되므로 얄짤없이 \(O(QN)\)이 된다.


Mo's algorithm의 경우 이 쿼리 옮기기가 적어지도록 쿼리를 잘 정렬하자는 아이디어에서 출발한다.


길이 \(B\)인 bucket으로 배열을 분할하자. 그리고 \(Q\)개의 쿼리를 다음의 comparator function으로 정렬한다.


두 쿼리 \([s_{1},e_{1}],[s_{2},e_{2}]\)를 정렬한다고 하자. 

- \(s_{1}\)과 \(s_{2}\)가 속한 bucket 번호가 같다면, \(e\)가 작은 쪽이 더 작다.

- 그렇지 않다면 bucket 번호가 작은 쪽이 더 작다.


이와 같이 정렬하고 위의 Naive 알고리즘을 적용하면 쿼리 옮기기의 횟수는 \(O(QB + \frac{N^2}{B})\)가 된다!

이유를 설명하려고 했지만 위의 블로그에 더 잘 쓰여 있기도 하고, 본론과는 거리가 머니 넘어가자.

증명을 직접하는 것도 나쁘지 않다. 쿼리를 bucket 안에서 움직일 때와, 다른 bucket으로 넘어갈 때로 나눠 생각해보자.


따라서 \(B = \sqrt{N}\)으로 잡으면 \(O\left((N+Q)\sqrt{N}\right)\)이고, 치졸하게 \(B = \frac{N}{\sqrt{Q}}\)로 잡으면 이론상 최적인 \(O(N\sqrt{Q})\)가 나온다. 물론 practical한 차이는 보이지 않고 코딩만 까다로워지니 착한 어린이들은 \(\sqrt{N}\)으로 잡자. 예외가 싫다면 \(\sqrt{N + 1}\)도 나쁘지 않다.


Hilbert MO : TSP와의 연관성


HilbertMO를 떠올릴 수 있는 가장 중요한 관찰은, 쿼리 옮기기를 하나의 TSP로 생각할 수 있다는 점이다!


쿼리로 주어지는 \([s_{i}, e_{i}]\)를 2D plane의 한 점으로 생각해보자. 그럼 1번의 쿼리 옮기기 횟수는 두 점의 맨해튼 거리(택시거리) 로 주어진다. 총 \(Q-1\)번의 쿼리 옮기기를 최소비용으로 수행한다는 것은 결국 맨해튼 거리공간에서의 Hamiltonian path를 찾는 문제와 동치가 된다!


이렇게 생각했을 때, bucket을 사용한 Mo's algorithm은 다음의 그림으로 표현할 수 있다. x좌표는 \(s\), y좌표는 \(e\)다. \(y \ge x\)가 성립해야 함에 주목하자.






그런데, 이런 Manhattan TSP에서는 space - filling curve를 이용한 점 sorting이 좋은 heuristic으로 알려져 있다.

그래서 여기에 space - filling curve인 Hilbert Curve를 가져온다! 


\(2^k \times 2^k\) board 위에 Hilbert Curve를 그린다고 하자. \((2^k \ge N)\)

이 때 이 Curve가 점 \((x,y)\)를 몇 번째로 방문하는지는 \(O( \lg N )\)만에 알 수 있다. 이 때 이 방문 순서를 기준으로 점들을 정렬한다.


이 경우 쿼리 옮기기의 횟수는 \(O(N \sqrt{Q})\)가 된다.




Practical Performance


상세한 벤치마킹 결과는 원본 링크에서 확인할 수 있다. 

랜덤 데이터에서의 경향성을 보자면, 대부분의 경우 Classic Mo's algorithm을 압도하는 performance를 보여주고 있다.

여담이지만 \(N\)이 크고 \(Q\)가 작은 경우의 압도적 performance 차이는 함정이다. 이 경우 \(B = \frac{N}{\sqrt{Q}}\)로 잡으면 큰 차이가 나지 않는다. 물론 그래도 Hilbert MO가 더 빠르다 ^^


실제로 BOJ 13545 - 수열과 쿼리 0을 이용해 벤치마킹한 결과 \(O(N\sqrt{Q}\lg N)\)짜리 풀이에서 1.4 ~ 1.7배의 성능 차이를 보인다.


주) 원래 저 문제는 저렇게 쌩 Mo질로 풀라고 만든 문제는 아니다. hilbertMO가 빠르다는 사실만 참조하자...

1 2 3 4 5