[알고리즘 개념] Query 문제 테크닉 Mo's 알고리즘

Mo's 알고리즘 이란?

구간 질의하는 Query 문제에서 업데이트되지 않는 특수한 상황에서 사용할 수 있는 알고리즘으로 기존의 구간 쿼리는 O(NM)인 반면 Mo's 를 사용하면 O(M sqrt N) 으로 줄일 수 있습니다. 

 

아이디어

데이터가 추가적으로 업데이트되지 않는다면, 모든 쿼리에 대해서 항상 전체를 탐색해줄 필요는 없습니다. 이 전에 계산한 구간의 값을 참고하여 답을 구할 수 있습니다. 

 

 

일단 데이터 길이를 N으로 했을 때 sqrt(N) 의 길이로 그룹을 나눕니다. 위 그림은 N = 10 일때의 그림이며 4개의 구간으로 나눌 수 있습니다. ( 왜 sqrt(N) 으로 나누는지는 아래에 설명하겠습니다 )

 

 

만약 위처럼 3가지 쿼리가 주어졌다고 할 때 어떻게 작동하는지 간략하게 그림으로 보고 자세히 설명해보겠습니다.

(처음 설명은 100% 맞는게 아니며 점점 보완하고 답을 내는 형식으로 진행하고 있습니다)

 

일단 첫 번째 쿼리에 대해 탐색을 완료했고 그 나머지 부분은 업데이트 되지 않았습니다. 

 두 번째 쿼리에 대해 업데이트할 때 이전이 상태에서 2와 7 부분을 삭제해주면 원하는 값이 나오게되고..

 

 

그 전의 쿼리의 상태에서 3을 삭제하고 7~10을 늘려주면 됩니다. 이런 방법은 당연히 O(NM)보다는 짧아 보이는데요... 여기서 첫 번째 쿼리는 무엇을 의미할까요? 그냥 첫 번째 입력의 쿼리일까요? 일단 아닙니다!

 

개선 사항 1

 

각 쿼리가 이전 쿼리와 겹쳐지지 않는 경우에는 O(NM) 이 발생합니다. 각 쿼리들이 최대한 겹치도록 배정하기 위해서 시작점을 오름차순으로 정렬해둔 후 정답 출력 부분에서 이를 고려하여 출력하면 됩니다. 

 

 

만약 위 사항을 고려하면 해결될까요? 정답은 아닙니다. 예시를 들면...

위와 같은 상황은 고려 사항 1을 만족합니다. 하지만 O(NM) 으로 TLE가 나올 것은 뻔합니다. 위와 같은 문제점을 분석하자면 Query의 시작점이 비슷한 곳에 뭉쳐있지만 끝 부분의 변동이 크다는 사실을 알 수 있습니다.

 

 

개선 사항 2

 

위의 문제 처럼 Query의 시작점이 어느 부근에 뭉쳐있다면 끝 부분이 긴 것 순서대로 처리하고 그 과정에서 시작점도 약간의 변동이 있지만 끝점의 심각한 변동보단 어느정도 짧은 길이의 변동이 보다 합리적인 것을 알 수 있습니다.

 

따라서 길이 K로 구간을 나누고 각 쿼리의 시작점이 속한 구간에 대해서 정렬할 때 속한 구간이 같다면 끝 부분의 위치로 정렬해줍시다.

 

 

개선 사항 3

 

데이터 길이가 N 이고 쿼리의 개수가 Q, 구간의 길이를 K로 할 때 시간복잡도를 계산해봅시다.

 

1) Query 시작값 변경, 구간 변경x

시작값은 i ~ i+K 까지 움직일 수 있기에 O(QK) 입니다

 

 

2) Query 시작값 변경, 구간 변경o

이전 구간의 기록을 지워야 하기 때문에 O(N) 만큼 소요됨을 알 수 있습니다.

 

 

3) Query 끝값 변경 ( 중요 )

 

만약 시작 부분이 속한 구간이 같다면 끝 값은 내림차순이기 때문에 O(N)의 시간복잡도를 가지게 됩니다. 하지만 시작 부분의 속한 구간이 달라지게 된다면 다시 O(N) 의 시간복잡도를 가지게 되므로 O(N) * O(구간의 개수) 라는 값을 가지게 됩니다.

 

 

위의 계산을 통해 O(N + QK + N * N/K) 임을 알 수 있었습니다 (정렬 O(NlogN) 은 제외했습니다. ) 위 식에서 N과 Q는 상수이므로 해당 값이 최소가 되는 K 값은 산술-기하 평균을 통해 K = sqrt(N) 일 때 시간복잡도가 최소가 된다는 사실을 알 수 있습니다. 

---

 

정리

 

1. 길이가 sqrt(N) 인 구간으로 나누고 시작값이 속한 구간 번호, 끝값 을 통해 입력값을 정렬한다.

2. 각 쿼리에 대해서 이전 쿼리에 대해서 추가/삭제할 구간을 업데이트해주고 해당 쿼리의 답을 구한다.

3. 해당 쿼리의 실제 입력 인덱스를 고려하여 정답을 출력한다.

 

예시 문제

 

수열과 쿼리 5(P2) : https://www.acmicpc.net/problem/13547

 

코드▼

#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> pii;
int N, M, A[100005], g, num[1000005], cnt, ans[100005];;

struct Query
{
    int s, e, idx;
    bool operator<(const Query&r) const{
        if(s / g != r.s / g) return s < r.s;
        return e < r.e;
    }
};
vector<Query> q;

int cal(int n, int val)
{
    if(val == -1 && num[n]==1) cnt--;
    if(val == 1 && num[n]==0) cnt++;
    num[n]+=val;
    return cnt;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>N;

    int x,y;
    for(int i=0;i<N;i++) cin>>A[i];

    cin>>M;
    for(int i=0; i<M; i++){
        cin>>x>>y;
        q.push_back({x-1,y-1,i});
    }
    g = sqrt(N);
    sort(q.begin(), q.end());

    int s=0, e=0;
    cal(A[0], 1);

    for(auto&i:q){
        int ns = i.s, ne = i.e;

        /// 이전 쿼리에 대해 추가/삭제 할 부분 업데이트

        for(int j=s; j<ns; j++) cal(A[j], -1);
        for(int j=s-1; j>=ns;j--) cal(A[j], 1);
        for(int j=e+1; j<=ne; j++) cal(A[j], 1);
        for(int j=e; j>ne;j--) cal(A[j],-1);
        s=ns, e=ne;
        ans[i.idx]=cnt;
    }
    for(int i=0;i<M;i++) cout<<ans[i]<<" ";
}

 

---

 

오프라인 쿼리나 lazy segment 를 다루기 전에 mo's를 다뤄봤는데요, 생각보다 재밌는 아이디어고 세그먼트 트리로 풀지 못하는 복잡한 상황에서 사용하기 좋은 것 같아서 다뤄봤습니다. 알고리즘 유도 과정과 증명을 통해 시간이 지나도 안 잊을 것 같네요 ㅎㅎ