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

Table of Contents

 

개요

쿼리 처리

쿼리 정렬

문제

 

 

 

1. 개요

 

 

 

 

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

 

 먼저 위의 문제를 읽어주시길 바랍니다.

 

 범위 쿼리를 처리하는 상황에서 가끔 이런 상황들이 있습니다. 배열 Array[1...N], 함수 Function, 범위 [L, R] 이 주어질 때

Function(Array[L], Array[L+1], ..., Array[R]) 계산하는데, 배열에 저장된 값을 고치는 update 연산은 없는 상황입니다. 위의 문제가 그 예시이지요.

 

 이런 상황을 만나면 Segment tree 나 Sparse table 로 접근하는 경우가 많습니다. 하지만 이 두 자료구조를 활용한 접근은 대체로, 온라인 처리가 아닌 배치 처리가 가능하다는 점을 사용하지 않습니다. 즉, 만일 이런 문제를 Segment tree 나 Sparse table 로 푼다면, 쿼리들의 순서에 상관 없이 답을 구할 수 있는 프로그램까지 짠 후, 굳이 주어진 쿼리 순서대로 답을 구해주는 꼴이 되는 것입니다.

 

 그런 점에서 착안해 배치 처리인 점을 먼저 공략하면, 풀 수 없던 문제를 풀거나 좀 더 쉬운 방법으로 문제를 풀 수 있는 경우가 있습니다. 이 때 사용하는 것이 Mo's algorithm 입니다.

 

 

 

2. 쿼리 처리

 

 Mo's algorithm 의 기본적인 아이디어는 배치 처리의 활용입니다. 즉, 쿼리의 순서를 마음대로 조작할 수 있다는 점을 이용합니다. 그렇다면 쿼리의 답을 구할 때, 이전 쿼리를 처리할 때 얻은 정보의 활용법을 고민해보는 건 당연한 수순일 것입니다.

 

 한 번 개요에 있는 문제에서 [Li, Ri] 에 대한 답을 통해, [L(i+1), R(i+1)] 을 구해보겠습니다. [Li, Ri] 에서 구한 서로 다른 수의 개수 만으로는 [L(i+1), R(i+1)] 에서의 답을 빠르게 구하기 힘들다는 건 금방 알 수 있습니다. [Li, Ri] 안에 어떤 수가 얼마나 있었느냐 에 따라 경우의 수가 나뉘기 때문이지요. 따라서 '[Li, Ri] 안에 어떤 수가 얼마나 있었느냐' 에 대한 정보를 추가로 저장해야 합니다.

 

COUNT[x] = ((A[j] == x) 인 j 의 갯수)

 -> COUNT[x] >= 1 이면 구간 안에 x가 존재하며, COUNT[x] == 0 이면 구간 안에 x가 존재하지 않는다는 의미가 됩니다.

 

 [Li, Ri] 에 대해 위와 같은 배열이 저장되어 있다면, O( | L(i+1) - Li | + | R(i+1) - Ri | ) 번의 연산으로 답을 구할 수 있습니다. [Li, Ri] 에서 [L(i+1), R(i+1)] 로 구간을 확장해 가면서, COUNT  배열을 갱신하면, '서로 다른 수의 갯수'도 같이 갱신할 수 있기 때문입니다. COUNT[x] 가 0에서 1로 갱신되면 '서로 다른 수의 개수'가 1 증가했다는 걸 알 수 있고, COUNT[x] 가 1에서 0으로 갱신되면 '서로 다른 수의 개수'가 1 감소했다는 걸 알 수 있지요. 자세한 방법은 아래 코드를 참고해주시길 바랍니다.

 

// code by RiKang, weeklyps.com
#include<stdio.h>
#include<algorithm>
#define PII pair<int,int>
#define PIII pair<PII,int>
 
using namespace::std;
 
const int N = 100005, M = 1000005, SQRT_N = 300;
PII query[N];
PIII order[N];
int cnt[M];
int a[N];
int n,q;
int an;
int ans[M];
 
void add(int idx){
    if(cnt[a[idx]]==0) an++; // 이번 추가로 새로운 수가 생김
    cnt[a[idx]]++;
}
 
void erase(int idx){
    cnt[a[idx]]--;
    if(cnt[a[idx]]==0) an--; // 이번 삭제로 한 수가 모두 사라짐
}
 
void go_query(PII prev, PII now){
    int l1 = prev.first;
    int r1 = prev.second;
    int l2 = now.first;
    int r2 = now.second;
    for(int i = l1-1; i>=l2; i--) add(i); // l1 > l2 인 경우, 구간이 늘어났으므로 노드 추가
    for(int i = r1+1; i<=r2; i++) add(i); // r1 < r2 인 경우, 구간이 늘어났으므로 노드 추가
    for(int i = l1; i<l2; i++) erase(i); // l1 < l2 인 경우, 구간이 줄었으므로 노드 삭제
    for(int i = r1; i>r2; i--) erase(i); // r1 > r2 인 경우, 구간이 줄었으므로 노드 삭제
}

 

 이처럼 a 에 이전 쿼리의 정답, cnt[x] = ((A[j] == x) 인 j 의 갯수) 이 저장되어 있다면 go_query([Li, Ri], [L(i+1), R(i+1)]) 을 통해 답을 갱신할 수 있습니다. ( * O( | L(i+1) - Li | + | R(i+1) - Ri | ) )

 

 하지만 아직 총 시간복잡도는 O(N^2) 으로 머물러 있습니다. 여기에서 시간복잡도를 줄이는 것은 배치 처리를 얼마나 활용하느냐, 즉, 쿼리를 어떻게 잘 정렬하는 지에 달려있습니다.

 

 

 

 

3. 쿼리 정렬

 

 

 

 

 위에서 구한 go_query() 함수를 활용하려면 'O( | L(i+1) - Li | + | R(i+1) - Ri | ) 의 합' 을 줄여야 합니다. 방법은 생각보다 간단한데, query를 { Li / sqrt(n) , Ri } 을 기준으로 정렬하면 끝입니다.

( * Li / sqrt(n) 을 기준으로 정렬, 만일 Li / sqrt(n)가 같다면 Ri 를 기준으로 정렬 )

 

 시간 복잡도를 알아보기 위해 먼저 O( | L(i+1) - Li | ) 의 총합을 알아보겠습니다.

 

(1)  Li / sqrt(n) == L(i+1) / sqrt(n) 인 경우

Li / sqrt(n) == L(i+1) / sqrt(n) 이기 때문에,  O( | L(i+1) - Li | ) <= sqrt(n) 임은 당연합니다.

-> (1) 의 경우를 모두 합해도 O( Q * sqrt(N) ) 이 됩니다. ( * Q = 쿼리의 갯수 )

 

(2)  Li / sqrt(n) != L(i+1) / sqrt(n) 인 경우

이런 경우는 최대 sqrt(n) 번 등장할 수 있습니다.( Li / sqrt(n) = 0 ~ sqrt(n) 만 가능하기 때문. )

| L(i+1) - Li | 의 최댓값은 N-1 입니다.

 -> (2) 의 경우를 모두 합해도 O( N * sqrt(N) ) 이 됩니다.

 

이제 O( | R(i+1) - Ri | ) 의 총합을 알아보겠습니다.

 

(1) Ri, R(i+1), R(i+2), ..., Rj가 한 블록 (Li / sqrt(n)가 모두 동일) 인 경우

R이 오름차순으로 정렬되어 있기 때문에 한 블록에서 | R(i+1) - Ri |의 총합은 Rj - Ri 입니다. 이는 N이하입니다.

그리고 블록은 총 sqrt(N)개 까지 있을 수 있습니다.

 -> (1) 의 경우를 모두 합해도 O( N * sqrt(N) ) 이 됩니다.

 

(2) Li / sqrt(n) != L(i+1) / sqrt(n) 인 경우

이런 경우는 최대 sqrt(n) 번 등장할 수 있습니다.( Li / sqrt(n) = 0 ~ sqrt(n) 만 가능하기 때문입니다. )

| R(i+1) - Ri |은 N이하입니다.

 -> (2) 의 경우를 모두 합해도 O( N * sqrt(N) ) 이 됩니다.

 

 위의 내용을 종합하면, 총 시간복잡도  = Q( (N+Q) * sqrt(N) * f(x) ) 임을 알 수 있습니다.

( * f(x) = add() 와 erase() 함수의 시간 복잡도, 이 예제에서는 O(1)입니다.)

 

 직관적으로 이해하기 위해선 이 쿼리들을 (x, y) = (Li, Ri) 인 점으로 2차원 좌표계에 찍어보면 편합니다.

 

// code by RiKang, weeklyps.com
#include<stdio.h>
#include<algorithm>
#define PII pair<int,int>
#define PIII pair<PII,int>
 
using namespace::std;
 
const int N = 100005, M = 1000005, SQRT_N = 300;
PII query[N];
PIII order[N];
int cnt[M];
int a[N];
int n,q;
int an;
int ans[M];
 
void add(int idx){
    if(cnt[a[idx]]==0) an++; // 이번 추가로 새로운 수가 생김
    cnt[a[idx]]++;
}
 
void erase(int idx){
    cnt[a[idx]]--;
    if(cnt[a[idx]]==0) an--; // 이번 삭제로 한 수가 모두 사라짐
}
 
void go_query(PII prev, PII now){
    int l1 = prev.first;
    int r1 = prev.second;
    int l2 = now.first;
    int r2 = now.second;
    for(int i = l1-1; i>=l2; i--) add(i); // l1 > l2 인 경우, 구간이 늘어났으므로 노드 추가
    for(int i = r1+1; i<=r2; i++) add(i); // r1 < r2 인 경우, 구간이 늘어났으므로 노드 추가
    for(int i = l1; i<l2; i++) erase(i); // l1 < l2 인 경우, 구간이 줄었으므로 노드 삭제
    for(int i = r1; i>r2; i--) erase(i); // r1 > r2 인 경우, 구간이 줄었으므로 노드 삭제
}
 
int main(){
    scanf("%d",&n);
    for(int i=1; i<=n; i++){
        scanf("%d",&a[i]);
    }
    scanf("%d",&q);
    for(int i=1; i<=q; i++){
        scanf("%d %d",&query[i].first, &query[i].second);
        order[i].first = PII(query[i].first/SQRT_N, query[i].second);
        order[i].second = i;
    }
    sort(order+1, order+q+1);
    for(int i=1; i<=q; i++){
        go_query(query[order[i-1].second], query[order[i].second]);
        ans[order[i].second] = an;
    }
    for(int i=1; i<=q; i++)
        printf("%d\n",ans[i]);
    return 0;
}

 

 

 

4. 문제

 

 

 

 

 

(0)

[BOJ 13547] 수열과 쿼리 5

 

 

 

풀이 : 본문 참고

 

 

 

(1) [BOJ 13548] 수열과 쿼리 6

 

 

 

풀이 링크

 

 

 

(2) [BOJ 8462] 배열의 힘

 

 

 

풀이 링크

 

※ 본문의 코드들은 C++ 17 환경에서 작성되었습니다.

※ 문의 : rikang93@gmail.com