Mo's Algorithm

BOJ 13547 문제를 기준으로 이 알고리즘을 설명하려고 한다.

이 문제는 [L, R] 쿼리가 입력되면, A[L], A[L+1], ..., A[R] 중 서로 다른 수의 개수를 출력하는 것이다.

 

Naive 한 풀이는 매우 쉬운데, 조금 덜 Naive 하게 생각해보자.

즉, 이전 쿼리에 대한 답을 알고 있다는 가정 하에, 현재 쿼리는 그 변화량만 계산해서 더해주면 된다.

이전 쿼리의 L, R 을 한 칸씩 움직이면서 현재 쿼리의 L, R 쿼리로 만들어준다.

이 때 숫자가 제거되거나 추가될텐데, 그에 맞게 답을 조정하는 간단한 방식이다. 

 

하지만 이 방법 또한 O(NQ) 로 TLE가 날 것이다.

Mo's Algorithm 은 오프라인 쿼리로, 이 방법을 그대로 적용하지만, 쿼리의 순서만 바꾸는 것이다.

재미있는 점은, O(NQ) 풀이가 쿼리를 제대로 정렬만 해주면 O((N+Q) root N) 가 된다는 점이다.

 

그렇다면, Q개의 쿼리들을 어떻게 정렬해주면 될까? 일단 (루트 N = sq) 라고 하자.

그러면, N 개의 숫자들은 길이 sq 짜리 구간 sq 개로 쪼개지게 된다.

 

이 때, 정렬 기준은 다음과 같다.

1. 우선 [L, R] 들을 R 이 속한 구간 번호의 오름차순으로 정렬한다.

2. 같은 구간에 속한 R 들에 대하여, 이들은 L 의 오름차순으로 정렬한다.

이렇게 정렬만 해주면 O((N+Q) root N) 이 된다. 왜 그럴까?

 

우선 L 의 입장에서 보자.

R이 속한 구간이 바뀌지 않는다면, L 은 오름차순으로 정렬이 되어 있을 것이다.

그렇다면 L 이 움직이는 횟수는 최대 O(root N) 이다.

R이 같은 구간 안에서 L 은 절대 더 작아질 수 없도록 정렬이 되어 있기 때문이다.

 

R이 속한 구간이 바뀐다면, L 은 최대 O(N) 만큼 움직이게 된다.

R이 속한 구간이 바뀌면 L 은 오름차순으로 정렬되어 있는 보장이 없다.

따라서 L 은 N 에서 1 로 확 바뀔 수도 있는 것이다. 1칸씩 가기에 최대 O(N) 만큼 이동한다.

하지만 R 이 속한 구간은 최대 root N 번만 바뀐다. 그렇게 정렬을 했기 때문이다.

따라서, L 입장에서 시간복잡도는 O(N root N) 이다.

 

이제 R의 입장에서 보자.

R이 속한 구간이 바뀌지 않는다면, R 은 최대 O(root N) 만큼 움직이게 된다.

R이 같으면 L 기준으로 정렬되기에, R 은 길이 sq 짜리 구간 내에서 정렬되지 않은채로 존재한다.

한 칸씩 가기 때문에 쿼리마다 최대 O(root N) 번의 이동을 하는 것이다.

매 쿼리가 R 이 속한 구간이 똑같다면 위 과정이 반복되므로 최대 O(Q root N) 이다.

 

R이 속한 구간이 바뀐다면, 최대 O(N) 만큼 움직이게 된다.

R은 한 칸씩 오른쪽으로 가면서 값을 갱신할 것이므로, 최대 O(N) 번 이동을 하는 것이다.

하지만 중요한 점은, 이 모든 과정을 합친 횟수가 O(N) 이라는 것이다.

R이 속한 구간은 절대 작아질 수 없기 때문에, 앞에 있는 구간으로 돌아갈 수가 없다.

따라서, R 입장에서 시간복잡도는 O(N + Q root N) 이다.

 

이로써 우리는 쿼리 정렬만 잘 해줘도 O((N+Q) root N) 으로 문제를 해결할 수 있다.

 

구현 시 유의사항 : sq = int(sqrt(N)) 까먹지 말기