[알고리즘] Mo's 알고리즘

Mo's 알고리즘은 중국 알고리즘 대회에서 Mo Tao라는 사람이 사용한 기법으로 유명해졌다. 그래서 컴퓨터공학 다른 곳에서는 찾기 힘든 알고리즘이고 Competitive Programming에서 볼 수 있는 알고리즘이다. 어떤 알고리즘인지 알아보자.

 

오프라인 쿼리

mo's 알고리즘을 알기 위해 오프라인 쿼리를 알아야 한다.

 

무방향 가중 그래프가 주어지고 쿼리마다 a, b를 연결하는 간선을 끊고 u, v번 노드가 서로 연결돼 있는지 판정하시오.

 

위와 같은 문제는 주어지는 쿼리마다 해결하려고 하면 굉장히 어렵다. 하지만 간선을 연결하는 문제라면 분리집합으로 쉽게 해결할 수 있다. 그래서 처음에 쿼리를 모두 저장하고 뒤에서부터 역순으로 쿼리를 수행하면 쉬울 것이다.

이런식으로 여러 개의 쿼리를 주어진 순서대로 처리하지 않고 임의의 순서로 재배열해서 처리하는 방법을 오프라인 쿼리 기법이라고 한다. 반대로 주어진 순서대로 처리하는 방법은 온라인 쿼리 라고 한다.(평범한 경우는 이렇게 해결한다.)

 

어떠한 쿼리문제를 해결하기 위해 온라인, 오프라인 모두 사용할 수 있다면 오프라인이 더 쉽게 해결될 여지가 있다. 온라인 쿼리는 오프라인 쿼리의 부분집합이기 때문이다. 또한 문제를 출제할 때 온라인 쿼리를 강제할 수 있다.

https://www.acmicpc.net/problem/17465

https://www.acmicpc.net/problem/14898

위 두 문제와 같이 이전 쿼리의 결과가 다음 쿼리의 범위에 영향을 미치면 오프라인으로 해결하기 굉장히 어려워진다. 또한 오프라인 풀이를 막는 것 만으로도 위 문제들과 같이 난이도가 눈에 띄게 어려워진다. 이처럼 오프라인 쿼리를 사용하면 어려운 쿼리문제를 쉽게 해결할 수 있다.

 

제곱근 분할법

제곱근 분할법은 Mo's 알고리즘의 핵심이다. Mo's 알고리즘을 사용하면 시간복잡도가 $O((N+Q)\sqrt{N})$이 나오는데 제곱근 분할법을 응용했기 때문에 이런 시간복잡도가 나오게 된다.

자세한 내용은 이 곳을 참고하자.

 

Mo's 알고리즘

이제 알아야 할 것을 모두 알았으니 Mo's 알고리즘을 알아보자. Mo's 알고리즘은 세그먼트 트리나 누적합 같은 기존에 알고 있던 자료구조로 해결하기 어려운 쿼리 문제를 수행한다. 예를 들면 서로 다른 수의 개수를 세는 쿼리나 특정 수가 몇번 등장했는지 세는 쿼리가 있다. 어떻게 쉽게 해결할 수 있는지 알아보자.

TL;DR

(구간의 왼쪽값을 $\sqrt{N}$으로 나눈 값, 구간의 오른쪽 값)을 기준으로 정렬하고 쿼리를 수행한다.

예... 이게 끝입니다...

핵심은 위의 순서대로 쿼리를 수행하지만 이전 쿼리를 처리할 때 사용한 데이터를 이어서 사용한다는 점이다.

알고리즘 작동 과정

https://www.acmicpc.net/problem/14897

이 문제를 Mo's 알고리즘으로 풀어보자.

예제 데이터

10
1 3 2 1 3 1 3 2 1 3
10
8 9
4 7
6 8
4 6
3 7
2 10
3 8
1 10
4 7
1 7

같은 색은 같은 버킷에 들어있는 수이다. 위에서 말한 대로 정렬하면 순서가 다음과 같다. (0-base기준으로 정렬하면 좋다.)

3 7
1 7
3 8
2 10
1 10
4 6
4 7
4 7
6 8
8 9

쿼리를 그림으로 나타냈다.

오른쪽 구간의 범위가 늘어나는 동안 왼쪽 구간은 같은 버킷에서만 움직인다. 또한 왼쪽 구간의 버킷이 이동하면 해당 버킷에 왼쪽 구간이 들어있는 구간들 중 가장 작은 오른쪽 구간을 가지는 쿼리부터 수행한다.

매 쿼리마다 왼쪽 구간은 한번에 $O(\sqrt{N})$만큼 움직일 수 있고 오른쪽 구간은 최대 $O(N)$만큼 움직일 수 있다.

왼쪽 구간은 최대 쿼리개수 $Q$만큼 처리하므로 총 $O(Q \sqrt{N})$이 걸린다.

오른쪽 구간은 왼쪽 구간의 버킷이 변화할 때마다 $O(N)$을 쓰게 되므로 총 $O(N \sqrt{N})$이 걸린다. (왼쪽 구간의 버킷은 최대 $\sqrt{N}$번 변한다!)

따라서 총 시간복잡도는 $O((N+Q)\sqrt{N})$이 된다.

서로 다른 수를 세는 것은 배열이나 map을 사용하여 카운팅을 하면 해결할 수 있다.

 

mo's 알고리즘은 배열에 변화가 있으면 사용하기 힘들다. 애초에 오프라인 쿼리가 변화를 받아들이기 힘들기 때문이다..

 

연습문제

https://www.acmicpc.net/problem/11659

https://www.acmicpc.net/problem/14897