Mo's algorithm (모스 알고리즘)

 

모스 알고리즘은 오프라인 쿼리 문제에서 쿼리의 순서를 최적화 시키는 알고리즘이다.


이는 전에 포스팅한 sqrt decomposition을 이용하여 구현하게 되는데 다음과 같은 문제를 생각해보자.


백준 13547


수열의 크기가 $N$이고, 쿼리의 갯수가 $M$일 때, 쿼리를 입력받은 대로 순차적으로 처리한다면 $O(NM)$으로 시간초과가 발생한다. 

그렇다면 우리가 이전 쿼리의 구간에서 사용했던 정보를 이용하여 현재 쿼리 구간의 정보를 더해 사용하는 것은 어떨까?


예를 들어  다음과 같은 식이다.


Qi에서  100 ... 10000 번째 까지의 $A_i$에 대하여 다른 수가 몇 번 등장했는지를 뽑아낸다면, 이 때 뽑아냈던 정보를 이용해


Qi_1에서 200 ... 9000 번째 까지의 $A_i$에 대하여 다른 수가 몇 번 등장했는지를 뽑아내는 것이다.


이는 100을 가르키는 왼쪽 포인터가 200까지 이동하면서 순차적으로 cnt 배열의 $cnt[Arr[l]]$을 -1로 update하고 또한 10000을 가르키는 오른쪽 포인터가 9000까지 이동하며 $cnt[Arr[l]]$을 -1로 update하면 정보를 이용하여 구할 수 있을 것이다.

이 때 cnt 배열이 0이 된다면 ans 값을 -1 하면 값 종류의 갯수가 하나 적어진다는 것을 뜻하게 되고,

cnt 배열이 0에서 0이 아닌 값이 된다면 ans 값을 1하면 값 종류 갯수가 하나 늘어난다는 것을 뜻하게 된다. 


이를 바탕으로 구현하면 다음과 같이 코드를 작성할 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
struct query {
    int left, right, index;
} Q[100001];
 
void f(int index, bool add) {
    if(add) {
        if(cnt[arr[index]] == 0) {
            disNum++;
        }
        cnt[arr[index]]++;
    }
    else {
        cnt[arr[index]]--;
        if(cnt[arr[index]] == 0) {
            disNum--;
        }
    }
}
 
...
 
 
int main() {
    ...
    int lo = 0, hi = 0;
    for(int i=1; i<=M; i++) {
        while(Q[i].right > hi) {
            f(++hi, true);
        }
        while(Q[i].right < hi) {
            f(hi--false);
        }
        while(Q[i].left < lo) {
            f(--lo, true);
        }
        while(Q[i].left > lo) {
            f(lo++false);
        }
        ans[Q[i].index] = disNum;
    }
 
    for(int i=1; i<=M; i++printf("%d\n", ans[i]);
}
cs


하지만 이것으로 불충분한것이, offline query를 정렬하지 않고 사용할 경우 최악의 시간복잡도가 

$O(NM)$이다. 왜냐하면 Q1이 (1, 1)까지의 query이고 Q2가 (N, N)까지의 query일 경우 포인터가 $O(N)$ 움직여야하고 이런 것이 M번 반복되면 $O(NM)$이기 때문이다.


그러면 offline query를 어떻게 정렬해야 할까?

여기서 전에 살펴본 sqrt decomposition을 생각해보자. 전체 N개의 블록에 대해서 $\sqrt{N}$개의 블록으로 쪼갠후 다음과 같이 정렬한다고 생각하자.


1
2
3
4
5
6
7
8
bool cmp(const query& a, const query& b) {
    int sq = (int)sqrt(N);
 
    int aSR = a.right / sq;
    int bSR = b.right / sq;
    
    return aSR == bSR ? a.left < b.left : aSR < bSR;
}
cs


query a의 오른쪽 포인터, query b의 오른쪽 포인터에 대하여 sq_block의 순서를 통해 query를 정렬한다.

만약 sq_block이 같을 경우  왼쪽 포인터를 비교한다.


자 이렇게 되면 먼저 오른쪽 포인터의 움직임을 생각하자.


오른쪽 포인터의 움직임은 첫째, 같은 sq_block내에서 움직이거나, 다른 블록으로 넘어가는 것임.

같은 sq_block내에서 움직일 경우, 이 경우는 모든 Query M에 대해서 $O(\sqrt{N})$만큼 움직이므로 $O(M\sqrt{N})$만큼 이동이 발생함.


자 그럼 다른 블록으로 넘어가는 경우는 어떨까?

한 번에 최대 $O(N)$칸을 움직여야 할수도 있지만, 전체 쿼리를 수행하는 데에 있어 블록 사이를 건너가는 이동 횟수도 총 $O(N)$이다. 이게 매우 중요한 포인트인데, 다른 block으로 넘어갈 경우, 이전에 있던 block으로 절대 돌아오지 않으므로 $O(N)$이 된다.


정리하면 M개의 쿼리에 대해 매 쿼리당 $O(\sqrt{N})$번을 움직이고 전체과정에서 $O(N)$번의 이동이 있으니 $O(N + M\sqrt{N})$번의 이동만 있게 된다.


왼쪽 포인터의 이동 같은 경우에는 r이 이전 쿼리와 같은 블록에 속해 있는 동안 총 $O(N)$번 움직인다.

r이 이전 쿼리와 다른 블록에 속해있을 경우가 $O(\sqrt{N})$으로, 이 경우 left pointer가 1로 초기화가 되기 때문에 총 $O(N\sqrt{N})$만큼 움직이게 된다.


따라서, 모스 알고리즘을 이용하면 $O((N+M)\sqrt{N})$ 시간에 문제를 풀 수 있다.

존내 개꿀이다.



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <stdio.h>
#include <math.h>
#include <algorithm>
 
using namespace std;
 
int N, M;
int cnt[1000001];
int arr[100001];
int ans[100001];
int disNum = 0;
 
struct query {
    int left, right, index;
} Q[100001];
 
bool cmp(const query& a, const query& b) {
    int sq = (int)sqrt(N);
 
    int aSR = a.right / sq;
    int bSR = b.right / sq;
    
    return aSR == bSR ? a.left < b.left : aSR < bSR;
}
 
void f(int index, bool add) {
    if(add) {
        if(cnt[arr[index]] == 0) {
            disNum++;
        }
        cnt[arr[index]]++;
    }
    else {
        cnt[arr[index]]--;
        if(cnt[arr[index]] == 0) {
            disNum--;
        }
    }
}
 
int main() {
    scanf("%d"&N);
    for(int i=1; i<=N; i++) {
        scanf("%d"&arr[i]);
    }
    scanf("%d"&M);
    for(int i=1; i<=M; i++) {
        scanf("%d%d"&Q[i].left, &Q[i].right);
        Q[i].index = i;
    }
    sort(Q+1, Q+M+1, cmp);
    int lo = 0, hi = 0;
    for(int i=1; i<=M; i++) {
        while(Q[i].right > hi) {
            f(++hi, true);
        }
        while(Q[i].right < hi) {
            f(hi--false);
        }
        while(Q[i].left < lo) {
            f(--lo, true);
        }
        while(Q[i].left > lo) {
            f(lo++false);
        }
        ans[Q[i].index] = disNum;
    }
 
    for(int i=1; i<=M; i++printf("%d\n", ans[i]);
}
cs

댓글

가장 많이 본 글