[알고리즘] 모스 알고리즘

모스 알고리즘(Mo's algorithm)은 오프라인(쿼리의 순서가 상관 없는) 구간 쿼리를 처리할 때 유용한 알고리즘으로, 간단히 소개하면 길이 N인 구간을 √N개 구간으로 쪼개고, 미리 쿼리들을 정렬해서 O(n√n)의 시간복잡도로 쿼리를 처리하는 알고리즘입니다.

우선 길이 N인 구간을 각 √N개의 원소를 가진 버킷(bucket)으로 쪼갭니다.

각 쿼리들은 시작점이 더 앞쪽의 버킷에 속하고, 끝점이 더 앞쪽에 있는 쿼리부터 처리해주면 됩니다. 간단히 쿼리의 정렬 함수를 수도코드로 표기하면 이렇게 될 것입니다.

bool cmp(query a, query b) {
    if (a.start/sqrt(n) < b.start/sqrt(n))
    	return true;
    else if (a.start/sqrt(n) == b.start/sqrt(n))
    	return a.end < b.end;
    return false;
}

쿼리를 정렬한 이후에는 투 포인터 알고리즘으로 문제를 해결하면 됩니다.

관련 문제

[BOJ] 수열과 쿼리 5 (www.acmicpc.net/problem/13547)

13547번: 수열과 쿼리 5

[BOJ] 수열과 쿼리 6 (www.acmicpc.net/problem/13548)

13548번: 수열과 쿼리 6