Mo’s Algorithm – 쿼리 순서만 바꿨을 뿐인데 속도가 10배 빨라진다고?

“수많은 쿼리를 정렬만 해도 빨라진다?”

이런 말도 안 되는 얘기가 진짜 가능할까?

가능합니다.
그게 바로 오늘 이야기할 Mo’s Algorithm입니다.
무엇보다 구현이 어렵지 않고, 원리도 명확해서 초보자도 도전해볼 수 있는 최적화 알고리즘이에요.

🧠 핵심 아이디어 요약

Mo’s Algorithm은 오프라인 구간 쿼리 최적화 알고리즘입니다.
arr[l..r]의 누적 정보를 빠르게 구하려고 할 때,
쿼리 순서만 잘 정리해주면
쿼리마다 O(1)~O(√N) 수준으로만 이동하며 처리할 수 있게 해줍니다.

📌 언제 쓰면 좋을까?

배열의 길이 N ≤ 10^5, 쿼리 개수 Q ≤ 10^5
쿼리: arr[L..R] 범위에서 특정 통계를 구하는 문제
but → **배열 갱신(Update)**는 없거나 적어야 함

🎯 대표 문제 예시

배열 A가 주어졌을 때, Q개의 쿼리가 주어진다.
각 쿼리 [L, R]에 대해,
해당 구간에 등장하는 서로 다른 수의 개수를 출력하라.

이걸 매 쿼리마다 O(N)에 하면 시간초과 납니다.
→ Mo's Algorithm 쓰면 전체 쿼리 처리 O(N√N) 가능.

📐 작동 방식 – 정렬이 핵심이다

쿼리를 블럭 단위로 나눈다 (예: √N 구간 단위)
블럭 기준 + R 기준 정렬
정렬된 순서대로 L, R 포인터를 이동시키면서 add()/remove()만 수행

BLOCK_SIZE = int(math.sqrt(n))
queries.sort(key=lambda x: (x.l // BLOCK_SIZE, x.r))

✅ 핵심 구현 구조

current_l = 0
current_r = -1
for q in queries:
    l, r = q.l, q.r

    while current_r < r:
        current_r += 1
        add(current_r)

    while current_r > r:
        remove(current_r)
        current_r -= 1

    while current_l < l:
        remove(current_l)
        current_l += 1

    while current_l > l:
        current_l -= 1
        add(current_l)

    answer[q.idx] = get_answer()

🛠 실전 예제 (백준 13547 - 수열과 쿼리 5)

문제 요약
N개의 수, Q개의 [L, R] 구간 쿼리
→ 각 구간에서 다른 숫자 개수 출력

from math import sqrt
from collections import defaultdict

class Query:
    def __init__(self, l, r, idx):
        self.l = l
        self.r = r
        self.idx = idx

BLOCK = 0
def mo_cmp(a: Query):
    return (a.l // BLOCK, a.r)

def mos_algorithm(arr, queries):
    global BLOCK
    BLOCK = int(sqrt(len(arr)))

    queries.sort(key=mo_cmp)
    answer = [0] * len(queries)
    freq = defaultdict(int)
    cnt = 0

    l, r = 0, -1
    for q in queries:
        while r < q.r:
            r += 1
            freq[arr[r]] += 1
            if freq[arr[r]] == 1:
                cnt += 1
        while r > q.r:
            if freq[arr[r]] == 1:
                cnt -= 1
            freq[arr[r]] -= 1
            r -= 1
        while l < q.l:
            if freq[arr[l]] == 1:
                cnt -= 1
            freq[arr[l]] -= 1
            l += 1
        while l > q.l:
            l -= 1
            freq[arr[l]] += 1
            if freq[arr[l]] == 1:
                cnt += 1

        answer[q.idx] = cnt
    return answer

✅ 실전 적용 팁

상황 해결법

쿼리 결과가 정렬되어 있지 않다	Query에 인덱스를 저장해 정렬 복원
숫자가 너무 크다	좌표 압축 활용
값이 추가/제거될 때 복잡하다	add() / remove() 함수 분리
R 우선 정렬이 더 빠를 때	Z 모양 정렬 (Hilbert order) 사용

🏁 마무리

Mo's 알고리즘은

쿼리가 많고
배열 변화는 없고
구간 통계만 필요할 때

진짜 믿고 쓰는 “오프라인 쿼리 최적화 도구”입니다.
다음 글에서는 이를 트리에 적용하는 방법인
👉 Mo’s Algorithm on Tree를 소개하겠습니다.

모스알고리즘, MoAlgorithm, 쿼리최적화, 구간질의, 파이썬알고리즘, 오프라인쿼리, 알고리즘트릭, 구간통계, 쿼리정렬, SEO 최적화 10개