개인적으로 공부하다가 그 심플함과 발상에 충격먹은 알고리즘 1순위 (2023/07 기준)

Mo's Algorithm을 내가 이해한 순서대로 한번 정리해보고자 한다.

TL;DR

Offline Query가 가능해야 함, 아래와 같이 쿼리 정렬

• $sqrtN = \sqrt N$

struct Q { // Query
    int s, e;
    int oidx; // Original Index
    bool operator<(const struct Q& t) const {
        if (e / sqrtN == t.e / sqrtN) return s < t.s;
        return e / sqrtN < t.e / sqrtN;
    }
};

Bucket Challenge

난 개인적으로 bucket을 활용한 풀이를 매우 좋아한다. 알고리즘 명으로는 Sqrt Decomposition으로 많이 부르는 기법인데, 전체 배열 크기가 $N$ 일때, 전체 구간을 $\sqrt N$ 으로 나누게 되면, 각 bucket의 크기 또한 $\sqrt N$이 된다. 이렇게 되면, 각 구간마다의 계산값(이를테면 구간마다의 합)을 구하는 데에 최대 $O(\sqrt N)$의 시간이 걸리게 되는 아름다운 결론에 도달한다.

예를 들어, 전체 구간 크기가 10000이면, 각 구간은 100으로 나눌 수 있고, 이 상태에서 각 구간의 합을 bucket[i/100]에 미리 계산해 두었다고 하자. 그러면, $[4, 303]$ 구간의 합은 미리 계산해둔 값들을 바탕으로 아래처럼 구하면 된다.

• A[4], A[5], A[6], ... A[99]
• bucket[1] (100 ~ 199의 합이 미리 계산되어 있다)
• bucket[2] (200 ~ 299의 합이 미리 계산되어 있다)
• A[300], A[301], ... A[303]

위에서 확인이 가능한 것처럼, bucket 외의 구간을 합해야 하는 수는 worst의 경우에도 $\sqrt N$을 넘지 않는다. 따라서 이런 경우 query 마다의 시간 복잡도는 최대 $O(\sqrt N)$이 된다고 할 수 있는 것이다.

Mo's Algorithm

바로 이러한 루트로 나누는 아이디어를 Offline query에 적용한 것이 Mo's Algorithm이다. Offline query 역시 발상이 독특한데, query를 꼭 입력이 들어온 순서대로 처리하지 않는 것을 말한다. 만약 아래와 같은 query가 반복된다고 해보자.

• $[1, 100]$
• $[1000, 1300]$
• $[2, 101]$
• $[1001, 1301]$
• $[3, 102]$
• $[1002, 1302]$

딱 봐도 query를 재배치하고 싶은 욕구가 생길 것이다. 재배치하면 이전에 계산한 값을 활용할 여지가 있기 때문이다. 다만, 재배치를 일반적으로 어떤 순서로 할 것인지가 막막하다. Sqrt Decomposition까지는 루트를 어떻게 활용할지에 대한 아이디어가 어느 정도 직관으로 찾아지지만, Mo's 정도 되면 쉽지 않다. 재배치 방식에 대해 아래처럼 생각을 해보는 것이 일반적일 것이다.

1. $[s, e]$에 대해서 s 먼저 정렬하면?
   • $[1, 100]$, $[1, 10000]$, $[2, 100]$, $[2, 10000]$ 처럼 질의가 올 수 있다.
2. $[s, e]$에 대해서 e 먼저 정렬하면?
   • 1과 같은 반례가 존재한다.
3. $[s, e]$에 대해서 s 먼저 정렬하고 같으면 e로 정렬하면?
   • 그럴싸 하지만, 전체적으로 비효율이 존재하는 것은 마찬가지이다.
   • 아래 케이스가 여전히 해결이 안된다.
   • $[1, 2]$, $[1, 10000]$, $[2, 3]$, $[2, 10001]$, ...

즉, 위처럼 단순 정렬 해서는 어떻게 정렬해도 쉽지 않다. Mo's Algorithm은 엄청난 발상에서 출발하는데, 바로 한쪽 구간에 루트를 취하는 것이다. 아래와 같은 operator를 통해 정렬하는 것을 생각해보자.

bool operator<(const struct Q& t) const {
    if (e / sqrtN == t.e / sqrtN) return s < t.s;
    return e / sqrtN < t.e / sqrtN;
}

$\sqrt e$가 같을 때 $s$를 활용해 오름차순으로 하고, 다를 때는 $\sqrt e$가 오름차순으로 정렬하는 것이다. 이렇게 하면, 처음의 예시가 아래처럼 깔끔하게 떨어진다. ($N = 10000$을 가정하자)

• $[1, 100]$ : e가 bucket 1에 속하므로 제일 먼저 온다.
• $[2, 101]$ : 위와 동일한 bucket이고, s의 순서에 따라 정렬되었다.
• $[3, 102]$
• $[1000, 1300]$ : e가 bucket 13에 속하므로 1번보다 나중에 온다.
• $[1001, 1301]$
• $[1002, 1302]$

직관으로 확인해봐도, query 간 이동할 때 걸리는 시간이 상당히 개선이 될 것이라고 짐작할 수 있다. s와 e가 이동하는 전체적인 거리를 생각해보자.

1. e는 전체적으로는 $O(N)$, 그리고 query 구간 내에서 $O(\sqrt N)$ 만큼 이동 가능하고, query수가 $M$개라고 하면, 총 $O(N + M\sqrt N)$ 만큼 이동할 수 있다.
2. s는 e가 최대 $O(\sqrt N)$ 만큼 이동하는 동안 오름차순 정렬되어 있으므로 최대 $N$만큼 이동가능하다. 즉, 총 $O(N\sqrt N)$ 만큼 이동할 수 있다.

1과 2를 둘 다 고려하면 최종적인 시간 복잡도인 $O((N + M)\sqrt N)$이 나온다.

Time Complexity

• 구간 길이 N이고, 쿼리 M개 일 때,
  • $O((N+M) \sqrt N)$

하나의 query를 수행하는 데에 걸리는 시간이 $O(1)$이 걸린다면, 전체적인 시간복잡도는 위에서 살펴본 것처럼 $O((N + M)\sqrt N)$이 된다. naive하게 전체 query를 처리했다면 $O(NM)$이 걸렸을 것이므로, 엄청난 개선이 된다고 할 수 있다.

참고 링크

• 소멤블로그 Mo's Algorithm 소개: https://infossm.github.io/blog/2019/02/09/mo's-algorithm/
• 백준 수열과 쿼리 5: https://www.acmicpc.net/problem/13547