Mo's

모스 알고리즘(Mo's Algorithm)은 업데이트가 없는 복잡한 구간 쿼리를 처리하는 알고리즘입니다.

 

시작하기 전, 선행지식으로 sqrt Decomposition과 오프라인 쿼리에 대해 알고 있어야 합니다.

sqrt Decomposition은 이에 대해 설명한 제 글이 있습니다.

https://anz1217.tistory.com/127

MITM, sqrt Decomposition

 

오프라인 쿼리는 생각보다 간단하니 이 글에 바로 설명합니다.

쿼리 문제를 풀 때, 대부분의 경우에 우리는 쿼리가 들어오자마자 처리하고 결과를 출력합니다.

하지만 잘 생각해보면, 쿼리를 굳이 입력이 들어오는 즉시 처리할 필요는 없습니다. 입출력 스트림은 별개로 작동하므로 모든 쿼리를 한 번에 다 받은 다음, 원하는 순서로 쿼리들을 처리하여 답을 한꺼번에 구하고, 원래 쿼리가 들어온 순서대로 답을 출력하는 방식으로도 문제를 풀 수 있기 때문입니다.

전자가 온라인 쿼리, 후자가 오프라인 쿼리입니다.

 

예를 들어 다음과 같은 문제를 푼다고 하면,

https://www.acmicpc.net/problem/16978

16978번: 수열과 쿼리 22

 

쿼리를 한꺼번에 받은 다음 2번 쿼리를 \(k\)가 작은 순으로 정렬하여 풀어나가면 더 쉽게 문제를 풀 수 있습니다.

각 2번 쿼리가 들어온 순서를 저장한 다음, 마지막에 그 순서대로 답을 출력하면 됩니다.

 

풀이 코드는 생략합니다.

---

https://www.acmicpc.net/problem/11659

11659번: 구간 합 구하기 4

 

 

물론 우리는 누적 합을 구해둔 다음 구간 합을 상수 시간에 계산하면 된다는 사실을 잘 알고 있지만, 연습을 위해 모스 알고리즘으로 문제를 풀어봅시다.

 

기본적으로 모스 알고리즘은 투 포인터와 비슷하게 작동합니다.

쿼리의 구간을 나타내는 두 개의 포인터를 유지해 나간다면, 다음 쿼리를 계산할 때 이전 쿼리의 결과를 어느정도 재활용하며 계산할 수 있습니다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
int n, m;
int a[100001];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    
    int lp = 1, rp = 0; // 구간 [l, r] 을 나타내는 두 포인터
    int sum = 0;
 
    while (m--)
    {
        int l, r; cin >> l >> r;
        while (l < lp) sum += a[--lp];
        while (l > lp) sum -= a[lp++];
        while (rp < r) sum += a[++rp];
        while (rp > r) sum -= a[rp--];
 
        cout << sum << '\n';
    }
}

 

하지만 이 방식으로 문제를 풀더라도 온라인으로 문제를 푼다면 최악의 경우 두 포인터가 각 쿼리마다 \(O(N)\)번씩 이동하기 때문에, 총 시간 복잡도 \(O(NM)\)로 너무 느립니다.

그런데 오프라인으로 문제를 푼다면 어떨까요? 이 문제 풀이 방식은 그대로 두고, 각 쿼리를 계산하는 순서만 적절히 바꿈으로써 시간복잡도를 개선할 수 있지 않을까요?

 

놀랍게도 가능합니다!

\(N\)개의 원소를 sqrt Decomposition에서 했던 것과 같이, \(\sqrt N\)개의 버킷으로 분할합시다.

이제 각 쿼리 (\([l, r]\))를 다음과 같이 정렬하여 풀면 됩니다.

1. \(l\)의 버킷 번호가 작은 순

2. \(l\)의 버킷 번호가 같다면, \(r\)값 자체가 작은 순

 

시간복잡도를 계산해 봅시다.

\(l\)의 버킷 번호가 작은 순으로 정렬했으므로, 왼쪽 포인터는 현재 쿼리에서 다음 쿼리를 계산하는데에 최대 \(O(\sqrt N)\)번만 움직이게 됩니다. 총 쿼리가 \(Q\)개라면, 왼쪽 포인터가 움직이는 횟수는 총 \(O(Q\sqrt N)\)회 입니다.

\(r\)은 버킷 번호가 같다면 비내림차순으로 정렬했습니다. 따라서 한 버킷에 대해 오른쪽 포인터는 \(O(N)\)번 움직이게 됩니다. 버킷이 총 \(\sqrt N\)개 이므로, 오른쪽 포인터가 움직이는 횟수는 총 \(O(N\sqrt N)\)회입니다.

 

따라서 총 \(O((N+Q)\sqrt N)\)의 시간복잡도로 문제를 풀어낼 수 있게 됩니다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
const int BK_SIZE = 320;
 
struct Query
{
    int l, r;
    int idx;
};
 
bool comp(Query a, Query b)
{
    int al = a.l / BK_SIZE;
    int bl = b.l / BK_SIZE;
 
    if (al != bl) return al < bl;
    return a.r < b.r;
}
 
int n, m;
int a[100001];
vector <Query> q;
int ans[100001];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 0; i < m; i++)
    {
        int l, r; cin >> l >> r;
        q.push_back({ l,r,i });
    }
 
    sort(q.begin(), q.end(), comp);
 
    int lp = 1, rp = 0; // 구간 [l, r] 을 나타내는 두 포인터
    int sum = 0;
 
    for (int i = 0; i < m; i++)
    {
        int l = q[i].l, r = q[i].r;
        int idx = q[i].idx;
 
        while (l < lp) sum += a[--lp];
        while (l > lp) sum -= a[lp++];
        while (rp < r) sum += a[++rp];
        while (rp > r) sum -= a[rp--];
 
        ans[idx] = sum;
    }
 
    for (int i = 0; i < m; i++) cout << ans[i] << '\n';
}

---

제 그룹의 문제집에서 연습 문제들을 관리하고 있습니다.
문제집의 문제들을 보고 싶으시다면, 가입 신청을 해 주세요.

 

+ 요즘 많이 가입 신청이 들어오고 있습니다만, 꼭 그룹에 가입하셔서 제 문제들을 푸실 필요는 없습니다.

solved.ac 에서 태그를 찾아 푸시거나 백준 단계별로 풀기 에서 문제를 찾아 푸셔도 충분합니다!

그룹은 단순히 제 개인용 알고리즘 문제집 정리 용도이니 참고해주세요!

https://www.acmicpc.net/group/7712

ANZ1217