Mo's 알고리즘을 내가 이해한 방식대로 설명해보기

지난번에 Dijkstra 알고리즘에 대해서 제가 이해한 방식대로 설명해봤었는데, 이번에는 Mo's 알고리즘을 제가 이해한대로 한 번 설명해보고자 합니다. 물론, 지난번과 같이 이건 제가 이해한대로 설명한 것이기 때문에 정확한 설명이 아닐 수 있습니다. 그래도 Mo's 알고리즘이 무엇인지를 이해하는데에는 도움이 되지 않을까 해서 글을 올려봅니다. 그 전에 Mo's 알고리즘이 무엇인지와 어떤 문제들을 해결할 수 있는지에 대해서 설명해보겠습니다.

 

Mo's 알고리즘은 무엇인가?

후술하겠지만 Mo's 알고리즘은 Sqrt-Decomposition(평방분할)의 아이디어를 차용해서 특이한 구간 쿼리들을 계산하는 테크닉 입니다. 구간 쿼리라면 Segment Tree를 주로 떠올리실텐데, 이 알고리즘의 시간복잡도는 Segment Tree보다 느리고 주로 업데이트 쿼리가 없는 경우에만 사용할 수 있습니다. (저는 잘 모르지만 이런 글처럼 업데이트 쿼리가 있더라도 사용할 수 있는 경우가 있는 것 같긴 합니다.)

 

그렇다면 왜 이 알고리즘을 사용하는가? 바로 이 알고리즘은 Segment Tree로는 잘 못 푸는 유형들의 쿼리를 해결할 수 있기 때문입니다. 기본 문제들의 쿼리 유형들을 한 번 볼까요?

 

• BOJ 13547 : 수열과 쿼리 5 - 쿼리 : [l,r] 범위 내에 서로 다른 수들의 개수 구하기
• BOJ 13548 : 수열과 쿼리 6 - 쿼리 : [l,r] 범위 내에서 가장 많이 등장하는 수의 개수 구하기
• BOJ 13546 : 수열과 쿼리 4 - 쿼리 : [l,r] 범위 내에서 같은 값의 원소들 중 제일 멀리 떨어진 거리 구하기

 

이처럼 구하고자 하는 쿼리들이 매우 특이합니다. 그래서 Segment Tree로는 쿼리 구조를 어떻게 짜야 하는가와 어떤 정보들을 각 노드에 저장해야 하는지를 떠올리기 매우 어렵습니다. 그런데 이번에 다룰 Mo's 알고리즘은 이를 해결할 수 있습니다.

 

Mo's 알고리즘에 대한 설명

제가 위에서 Mo's 알고리즘을 활용하는 문제들을 설명했지만 난이도가 매우 높습니다. 그래서 구간 쿼리 입문용 문제를 들고와서 이걸로 설명해보겠습니다. 

 

BOJ 11659 : 구간 합 구하기 4 - 쿼리 : [l,r] 범위의 모든 원소들의 합 구하기

 

물론 이 문제의 정해는 Prefix Sum을 활용해서 O(N+Q)가 정해긴 하지만, 업데이트 쿼리가 없으면서도 구하고자 하는 쿼리가 매우 간단한지라 이 문제로 설명해보도록 하겠습니다.

 

우선, 예제로 설명하긴 너무 작으니 데이터를 좀 더 늘려볼까요?

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

 

이 정도면 충분할 것 같습니다. 이제 이 예제 가지고 설명해보도록 하겠습니다.

 

일단 Mo's 알고리즘의 아이디어는 "쿼리들을 어떻게 효율적인 순서로 배치해서 다음 쿼리를 계산할 때 지금 계산한 쿼리 값을 재활용 할 수 있지 않을까?" 에서 시작합니다. 지금 예제 데이터만 보더라도 만약에 우리가 5번째 쿼리([2,7])를 처리하고 2번째 쿼리([3,7])를 처리한다면 5번째 쿼리 값에서 2번째 element를 값을 빼는 것만으로도 2번째 쿼리에 대한 답을 찾을 수 있겠죠?

 

그러면 쿼리 순서를 어떻게 하면 잘 정리할 수 있을까요? 일단 각 쿼리를 [s,e]로 시작점이 s, 끝점이 e라 표현하겠습니다.

그러면 s가 동일한 쿼리는 e가 작은 순서대로 처리하면 시작점이 s인 모든 쿼리에 대해서 O(N)만에 구할 수 있습니다.

 

그렇다면 쿼리들을 [s,e] 순서대로 정렬해봅시다.

// 쿼리들을 [s,e]로 정렬한 결과
1. [1,2]
2. [1,5]
3. [2,4]
4. [2,7]
5. [3,7]
6. [5,8]
7. [6,7]
8. [7,9]
9. [8,8]

 

이렇게 처리한다면 시간복잡도는 어떻게 될까요? 우선 시간복잡도 설명이 길어질 것 같으니 몇 개의 기호를 미리 정하고 생각해봅시다. 아래와 같이 정의하면서 설명해보겠습니다.

 

• O(A) = 전의 쿼리의 s와 현재 쿼리의 s가 동일할 시에 생기는 비용
• O(B) = 전의 쿼리의 s와 현재 쿼리의 s가 차이가 날 시에 생기는 비용
• O(C) = 전의 쿼리의 e와 현재 쿼리의 e가 차이가 날 시에 생기는 비용
• O(T(n)) = 전의 쿼리의 s나 e를 현재 쿼리 s와 e에 맞출려고 한 칸 움직일 때에 드는 비용

 

이렇게 정의를 해둔다면 모든 쿼리를 처리하는 데 총 시간복잡도는 O(Q * (A + B + C) * T(n)) 이 됩니다. 예제 문제에서 O(T(n))은 s나 e가 한 칸 움직일 때 해당 element를 지우거나 더하면 되니 O(1)로 계산이 됩니다. 그래서 시간복잡도 분석은 O(Q * (A + B + C))만 고려하면 됩니다.

 

일단 O(Q * (B + C)) 에 대해서 먼저 알아보도록 하겠습니다. e는 쿼리에 등장하는 각 s에 대해서 최대 N번씩 옮깁니다. 또한, 쿼리가 s를 기준으로 정렬이 되어있으므로 s는 최대 N번 움직입니다.  그러면  O(Q * B) + O(Q * C) =  O(s가 움직이는 최대 횟수) + O(e가 움직이는 최대 횟수) = O(N) + O(N^2) = O(N^2) 이라는 결과가 나옵니다. 

 

O(Q * A)는 딱히 (지금은) 고려하지 않아도 됩니다. 왜냐하면 위에서 O(Q * C)의 계산을 하면서 s가 동일할 때에 대해서 시간복잡도 계산을 끝냈기 때문입니다. 그래도 각 쿼리들을 살펴보긴 해야하니깐 O(Q)가 됩니다. 따라서 총 시간복잡도는 O(Q+N^2)이 됩니다. 이렇게 풀면 당연히 시간초과가 납니다. 좀 더 최적화 할 방법이 없을 까요?

 

이렇게 한 번 생각해봅시다. 만약에 쿼리들을 정렬할 때 s의 차이가 별로 안 나는 것들끼리 묶어보면 어떨까요? s가 1,2인 것끼리 같이, 3,4인 것끼리 같이... 이렇게 2개씩 묶어서 정렬해봅시다.

// 새롭게 쿼리들을 정렬한 결과
1. [1,2]
2. [2,4]
3. [1,5]
4. [2,7]
5. [3,7]
6. [6,7]
7. [5,8]
8. [8,8]
9. [7,9]

 

이렇게 정리하면 시간복잡도가 어떻게 달라질까요? 우선 O(A), O(B)의 정의를 다시 새롭게 해야합니다. 재정의된 O(A), O(B), O(C)는 다음과 같습니다.

 

• O(A) = 전의 쿼리의 s 묶음과 현재 쿼리의 s 묶음이 동일할 때 생기는 비용
• O(B) = 전의 쿼리의 s 묶음과 현재 쿼리의 s 묶음이 차이가 날 시에 생기는 비용

 

이제 다시 O(Q * (A + B + C) * T(n))을 계산해보겠습니다.

 

우선 우리는 이제 O(Q * A)도 분석해보아야 합니다. 왜냐면 이제 현재 쿼리의 s 묶음이 전의 쿼리의 s묶음과 동일하더라도, s값 자체에는 차이가 있을 수가 있습니다. 다만, 다르더라도 실제로 최대 움직이는 횟수는 1칸이므로 O(Q*A)는 O(Q)가 됩니다.

 

이제 뒤에 O(Q * B) + O(Q * C)도 바뀌는데, 쿼리는 이제 s묶음을 기준으로 정렬이 되어있습니다. s 묶음의 크기는 2이므로 따라서, s의 묶음은 최대 N/2번 달라지게 됩니다. 그래서, O(Q * B) = O(N / 2)가 됩니다. 그리고 이제 e는 각 s의 묶음 별로 최대 N번 움직이기 때문에, O(Q * C) = O(N * (N / 2)) = O(N^2 / 2)가 됩니다. 그래서 총 시간복잡도는 O(Q) + O(N / 2) + O(N^2 / 2) = O(Q + N^2 / 2)로 바뀝니다. 

 

이러한 패턴을 알았으면 눈치채셨을 겁니다. 우리가 쿼리 내에 s를 K개씩 한 묶음으로 묶고 정렬을 한다면 총 시간복잡도는 O(K*Q+N^2/K)라는 결과가 나옵니다! 그러면 이 식을 어디까지 최적화 할 수 있을 까요? 바로 K = sqrt(N)으로 두면 최적화가 됩니다. K = sqrt(N)이라 두면 총 시간복잡도는 O((Q+N) * sqrt(N) * T(n)) = O((Q+N) * sqrt(N))이 됩니다.  여기서 K = sqrt(N) 아이디어는 Sqrt-Decomposition 아이디어랑 비슷하죠?

 

그래서 실제로 Mo's 알고리즘은 위에서 쿼리들의 순서들을 재배치하는 Offline-Query 테크닉을 사용하는데, [floor(s/sqrt(N)), e]를 기준으로 정렬해서 풉니다. 다만, sqrt(N)은 Sqrt-Decomposition 알고리즘 처럼 사실 정확하게 sqrt(N)로 둘 필요는 없고 적당한 크기로 지정해주어도 됩니다. 그리고 구현 팁이라면 범위를 늘리는 순서를 먼저 실행하고 이를 줄이는 방향으로 구현하는 게 더 좋습니다. 

 

아래 코드는 위의 예제 문제를 Mo's 알고리즘으로 푼 풀이 코드입니다. 생각보다 코드가 간결하죠?

#include<bits/stdc++.h>
#define ll long long

using namespace std;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    ll N, Q;
    cin >> N >> Q;
    
    vector<ll> v(N);
    for(int i =0; i<N; ++i) cin >> v[i];
    
    vector<tuple<ll,ll,ll,ll>> Queries(Q);
    vector<ll> ans(Q);

    for(int i = 0; i < Q; ++i){
        ll s, e;
        cin >> s >> e;
        --s; --e;
        Queries[i] = {s/sqrt(N), e, s, i};     
    }

    sort(Queries.begin(), Queries.end());
    // s/sqrt(N)을 우선적으로 정렬, 같으면 e를 우선적으로 정렬.

    ll curr_ans = 0; // 쿼리에 대한 답 기록용 변수.

    ll sqrt_s, e, s, idx;
    tie(sqrt_s, e, s, idx) = Queries[0];
    for (int i = s; i <= e; ++i){
        curr_ans += v[i];
    }
    ans[idx] = curr_ans;
    /// 첫 쿼리는 O(N)이긴 하지만 총 시간복잡도는 O(N * sqrt(N))이 있어서 무시됩니다.

    for(int i = 1; i < Q; ++i){
        ll sqrt_s, n_e, n_s, idx;
        tie(sqrt_s, n_e, n_s, idx) = Queries[i];

        while(n_s < s) curr_ans += v[--s];
        while(n_e > e) curr_ans += v[++e];
        // 범위 증가
        
        while(n_s > s) curr_ans -= v[s++];
        while(n_e < e) curr_ans -= v[e--];
        // 범위 감소
        
        ans[idx] = curr_ans;
    } 
    
    for(auto answer : ans){
        cout << answer <<"\n";
    }
    
    return 0;
} // Offline Query + Mo's Algorithm

 

이렇게 오늘 Mo's 알고리즘에 대해서 글을 써봤습니다. 이 알고리즘의 진가는 사실 위에 제가 예시로 든 수열과 쿼리 문제들에서 엄청 느낄 수 있는데, 저는 Segment Tree가 못 푸는 독특한 쿼리들을 풀 수 있다는 점에서 이 알고리즘을 꽤 흥미롭게 공부했었습니다. 제 글을 통해서 이 알고리즘에 대해서 어느 정도 이해하는데 도움이 되셨다면 좋겠습니다 :)

 

[참고] - 저는 아래 글들에서 Mo's 알고리즘을 배웠습니다! 

• https://blog.naver.com/kks227/221401154455
• https://justicehui.github.io/hard-algorithm/2019/06/17/MoAlgorithm/

 

혹시 Sqrt-Decomposition과 Offline Query를 모르는 분들을 위한 간략한 설명

- Sqrt-Decomposition (평방 분할 / 버킷 알고리즘)

 

N개의 칸을 대강 sqrt(N)개의 칸 씩 한 구간으로 나누어서 처리하는 방법입니다. 그렇다면 총 sqrt(N)개의 구간이 생겨서 구간 쿼리에 대해서 대강 sqrt(N)개의 구간만 보면 됩니다. (여기서 '대강'이라는 수식어를 붙인 이유는 실제 구현시에는 정확히 sqrt(N)이 아니라 적당한 값을 잡아서도 구현하기 때문입니다. 만약에 N = 100'000 일때 sqrt(N)이 316 정도이니 300 정도로 잡아서도 구현해요.)

 

구간이 겹치면 O(1)만에 대답, 걸치면 최대 O(sqrt(N))만큼만 보면 되어 각 쿼리별로 O(sqrt(N))만에 대답이 가능합니다. 이렇게 보면 또 Segment Tree 하위 테크닉 같은데... 업데이트가 O(1)인 점이 장점입니다. 또한, Segment Tree로는 안 되지만 이 테크닉으로 풀리는 문제들도 존재합니다. (예 : BOJ 17410, BOJ 13545) 

 

- Offline Query

 

쿼리의 순서를 재정렬해서 문제를 더 쉽게 푸는 방법론입니다. 구간 쿼리에서 이 테크닉을 사용하는 예시로는 BOJ 16978이 있습니다. 만약에 2번 쿼리에 대해서 k를 오름차순으로 정렬을 해준다면? 1번 쿼리가 총 k번 적용되었을 때 각각 답을 해주기도 편하겠죠? 이런식으로 쿼리의 순서들을 바꿔서 문제를 더 쉽게 풀 수 있습니다.

 

구간 쿼리랑은 주로 Mo's랑 많이 엮입니다. 그런데 이거 외에도 그래프 문제에서도 '간선을 제거하는 쿼리'로 DSU랑 엮어서 같이 나오는 경우도 있습니다. (예 : BOJ 15586, BOJ 12012, BOJ 17398)