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

모스알고리즘이란?

모스 알고리즘은 업데이트가 없는 구간 쿼리들을 처리하는 알고리즘이다.

기본 아이디어는 업데이트가 없기 때문에 '앞에서 계산된 값을 최대한 활용하자'이다.

특히 조회만 하는 경우는 쿼리의 순서를 자유롭게 바꿀 수 있는 환경에서 미리 계산된 값을 다시 이용할 수 있을 것이다.

이전에 살펴 보았던 제곱근분할법(https://wondangcom.tistory.com/2721) 을 이용하여 모스알고리즘을 구현 할 수 있는데 이 알고리즘으로 해결할 수 있는 문제는 원소의 수정은 없고 구간 내에서 어떤 결과를 찾는 종류의 쿼리만 있는 문제이다.

그렇다면 기존 문제보다 활용범위가 좁은 것은 아닐까?

간혹 세그먼트 트리 등을 이용해서 해결하지 못하는 경우가 발생한다. 이러한 문제 유형은 아래에서 살펴 볼 예정이다.

먼저 이 알고리즘이 어떻게 동작하는지 살펴 보자.

 

모스알고리즘 구현

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

위와 같이 배열에 데이터가 들어가 있는 경우 구간합을 구하는 쿼리를 살펴 보자.

쿼리 [1,7] 와 [3,6] 을 처리해야 한다고 해 보자.

쿼리[3,6]을 먼저 처리하고 [1,7]을 처리한다고 하면 [3,6]을 처리 했으므로 포함되지 않은 구간을 제외하고 나머지 원소들만 처리하면 [1,7] 구간의 결과를 알 수 있을 것이다.

이 때 쿼리의 순서를 두번째 쿼리를 먼저 수행하고 그 다음 첫번째 쿼리를 하는 것처럼 순서를 바꾸어 처리한다면 더 빠르게 처리 할 수 있다.

 

구현 방법은 다음과 같다.

[L_i,R_i] 형태의 쿼리들을 다음과 같은 우선 순위에 따라 순서를 바꾼다.

• L_i / √N 기준으로 오름차순으로 정렬한다.(여기서 √N으로 나누는 것이 제곱근분할법 의 구간번호)
• L_i / √N 가 서로 같다면, R_i 기준 오름차순 정렬한다.

그 다음으로 투포인트를 사용하는 것과 같이 필요한 부분은 반영,빠져야 하는 부분은 제외 시킨다.

 

예제) 백준 구간합 구하기 4 를 모스알고리즘을 이용하여 해결해 보자.

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

11659번: 구간 합 구하기 4

입력 예제를 다음과 같이 만들어서 생각해 보자.

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

√N 으로 나눈 값은 다음과 같이 될것이다.

4 6 => 4/3 6/3 = 1 2
1 8 => 1/3 8/3 = 0 2
8 9 => 8/3 9/3 = 2 3
3 4 => 3/3 4/3 = 1 1
6 9 => 6/3 9/3 = 2 3

조건에 맞춰 정렬하면 다음과 같다.

1 8 => 1/3 8/3 = 0 2
3 4 => 3/3 4/3 = 1 1
4 6 => 4/3 6/3 = 1 2
8 9 => 8/3 9/3 = 2 3
6 9 => 6/3 9/3 = 2 3

이렇게 되면 1~8 까지의 합을 구한 다음 3~4를 구할 때 1~2 의 값을 빼고 5~8의 값을 빼고

그 다음 4~6을 구할 때 3을 빼고 5~6을 더하는 식으로 연산을 하게 된다.

구현은 다음과 같다.

	for(int i=1; i<=n; i++){
		cin >> arr[i];
	}
	for(int i=0; i<q; i++){
        cin >> s >> e;
		qry.push_back({i, s, e});
	}
	sort(qry.begin(), qry.end());

	int s = qry[0].s
    int e = qry[0].e;
    //첫번째 쿼리의 합을 구한다
	for(int i=s; i<=e; i++){
		res += arr[i];
	}
	ans[qry[0].seq] = res; //해당 위치의 정답을 기록

	for(int i=1; i<q; i++){ //다음 쿼리를 하나씩 수행
		while(s < qry[i].s) res -= arr[s++]; //s 위치보다 뒷쪽이면 빼면서 오른쪽으로 이동
		while(s > qry[i].s) res += arr[--s]; //s 위치보다 앞쪽이면 더하면서 왼쪽으로 이동
		while(e < qry[i].e) res += arr[++e]; //e 위치보다 뒷쪽이면 더하면서 오른쪽 이동
		while(e > qry[i].e) res -= arr[e--]; //e 위치보다 앞쪽이면 빼면서 왼쪽으로 이동
		ans[qry[i].seq] = res;
	}
	for(int i=0; i<q; i++) cout << ans[i] << "\n";

 

그럼 진짜로 모스 알고리즘으로만 풀리는 문제를 살펴 보자.

 

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

13547번: 수열과 쿼리 5

구간에 존재하는 서로 다른 수의 개수를 출력하는 문제이다.

코드는 다음과 같다.

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

struct query{
    ll idx,s,e;
};
struct query qer[1010101];
ll ans[1010101];
ll cnt[1010101];
ll arr[1010101];
ll group;
ll now;
ll lf,rf;
bool compare(const struct query &l,const struct query &r)
{
    if(l.s/group!=r.s/group) return l.s<r.s;
    return l.e<r.e;
}
void queryDel(ll s, ll e){
    ll i;
    for(i=s;i<=e;i++)
    {
        cnt[arr[i]]--;
        if(cnt[arr[i]]==0) now--;
    }
}
void queryAdd(ll s,ll e){
    ll i;
    for(i=s;i<=e;i++){
        if(cnt[arr[i]]==0)now++;
        cnt[arr[i]]++;
    }
}
int main(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    freopen("input.txt","r",stdin);
    ll i,j,k,l,m,n,Q;
    cin >> n;
    group=sqrt(n);
    for(i=1;i<=n;i++)cin >> arr[i];

    cin >> Q;
    for(i=1;i<=Q;i++){
        cin >> qer[i].s >> qer[i].e;
        qer[i].idx=i;
    }
    sort(qer+1,qer+1+Q,compare);
    for(i=qer[1].s;i<=qer[1].e;i++){
        if(cnt[arr[i]]==0)now++; ///현재까지 들어 오지 않은 수라면 갯수를 세어 주자.
        cnt[arr[i]]++;
    }
    ans[qer[1].idx]=now;
    ll left=qer[1].s;
    ll right=qer[1].e;

    for(i=2;i<=Q;i++){
        if(qer[i].s<left) queryAdd(qer[i].s,left-1); ///왼쪽을 추가하자.
        if(qer[i].e>right) queryAdd(right+1,qer[i].e); ///오른쪽을 추가하자.
        if(qer[i].s>left) queryDel(left,qer[i].s-1);  ///왼쪽을 삭제하자.
        if(qer[i].e<right) queryDel(qer[i].e+1,right); ///오른쪽 을 삭제하자.
        left=qer[i].s;
        right=qer[i].e;
        ans[qer[i].idx]=now;
    }
    for(i=1;i<=Q;i++) cout << ans[i] << "\n";
}

s가 이동하는 시간 복잡도

바로 이전 쿼리와 s/√N  이 같다면 시작점은 아무리 많이 떨어져 있어도 O( √N ) 만큼 차이가 난다.

이 때 s/√N 는 단조 증가 하므로 모든 쿼리의 시작점은 최대 O(N) 번 바뀐다. 따라서 이동 횟수는 총 O(N√N)번 이동한다.