수업 목표
본 수업은 복잡한 오프라인 쿼리 처리, 다차원 누적 합, 최대 부분 구간 합의 고차원 확장, 그리고 동적 계획법 최적화 기법을 이해하고 구현하는 역량을 목표로 합니다.
- 모 알고리즘(Mo's Algorithm)을 활용하여 구간 쿼리를 $O((N + Q)\sqrt{N})$에 오프라인으로 일괄 처리합니다.
- 2차원 누적 합(2D Prefix Sum)을 구축하여 임의의 부분 직사각형 합 쿼리를 $O(1)$에 응답합니다.
- 1차원 카데인 알고리즘을 2D로 확장하여 $O(N^2 M)$에 최대 합 부분 직사각형을 탐색합니다.
- 분할 정복 DP 최적화(Divide and Conquer DP)를 이해하고 $K$ 그룹 분할 최소 비용 문제에 적용합니다.
학습 동기부여
데이터베이스에서 특정 날짜 범위의 집계 값을 실시간으로 계산하거나, 지도 위의 특정 직사각형 영역의 강수량 합계를 즉각 제공해야 하는 상황을 생각해 보세요. 수백만 개의 레코드를 그때마다 순회하면 몇 분이 걸릴 수도 있지만, 누적 합 배열을 미리 구축해 두면 4번의 배열 접근만으로 답이 도출됩니다. 마찬가지로, Mo's Algorithm은 중복 계산을 최소화하는 영리한 쿼리 정렬로 수십만 개의 구간 쿼리를 실시간 처리 수준으로 단축시킵니다. 이 단원에서 배우는 기법들은 경쟁 프로그래밍의 '고급 최적화'에 해당하지만, 동시에 실제 대용량 데이터 시스템에서 보편적으로 활용되는 핵심 원리이기도 합니다.
도입 스토리
동전 세기 게임을 상상해 봅시다. 긴 동전 수열이 있고 매번 "A번에서 B번까지 서로 다른 동전은 몇 종류?"라고 묻습니다. 처음엔 매번 A~B 전체를 세지만, 쿼리가 수십만 건이 되면 이는 불가능합니다. 그래서 쿼리들을 영리하게 정렬하고, 이전 구간 결과에서 포인터를 조금씩 이동시켜 답을 갱신하는 Mo's Algorithm이 등장합니다. 비유하자면, 같은 구역을 여러 번 답사하는 대신 구역별로 묶어 효율적으로 순회하는 우편 배달부 전략입니다.
1. Mo's Algorithm — 구간 쿼리 오프라인 처리
Mo's Algorithm은 쿼리를 블록 크기 $B = \sqrt{N}$ 기준으로 정렬한 뒤, 왼쪽/오른쪽 포인터 $l, r$을 이동시키면서 각 이동 시 현재 통계를 $O(1)$에 갱신하는 방식입니다. 총 시간 복잡도는 $O((N + Q)\sqrt{N})$입니다.
# 8073번: 구간 서로 다른 수 — Mo's Algorithm
import sys
from collections import defaultdict
input = sys.stdin.readline
def solve_mo():
n, q = map(int, input().split())
arr = list(map(int, input().split()))
queries = []
for i in range(q):
l, r = map(int, input().split())
queries.append((l - 1, r - 1, i)) # 0-indexed
block = max(1, int(n ** 0.5))
queries.sort(key=lambda x: (x[0] // block, x[1] if (x[0] // block) % 2 == 0 else -x[1]))
cnt = defaultdict(int)
ans = [0] * q
cur = 0
l, r = 0, -1
def add(idx):
nonlocal cur
if cnt[arr[idx]] == 0:
cur += 1
cnt[arr[idx]] += 1
def remove(idx):
nonlocal cur
cnt[arr[idx]] -= 1
if cnt[arr[idx]] == 0:
cur -= 1
for ql, qr, qi in queries:
while r < qr: r += 1; add(r)
while l > ql: l -= 1; add(l)
while r > qr: remove(r); r -= 1
while l < ql: remove(l); l += 1
ans[qi] = cur
print('\n'.join(map(str, ans)))
solve_mo()
2. 2차원 누적 합 (2D Prefix Sum)
2차원 배열에 대해 $P[i][j] = P[i-1][j] + P[i][j-1] - P[i-1][j-1] + A[i][j]$로 누적 합 배열을 구축합니다. 이후 임의의 부분 직사각형 $(r_1, c_1, r_2, c_2)$의 합은 포함-배제 원리로 $O(1)$에 계산됩니다.
# 8074번: 2D 구간 합 쿼리 — 2D Prefix Sum
import sys
input = sys.stdin.readline
def solve_2d_prefix():
n, m, q = map(int, input().split())
ps = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
row = list(map(int, input().split()))
for j in range(1, m + 1):
ps[i][j] = row[j - 1] + ps[i - 1][j] + ps[i][j - 1] - ps[i - 1][j - 1]
out = []
for _ in range(q):
r1, c1, r2, c2 = map(int, input().split())
ans = ps[r2][c2] - ps[r1 - 1][c2] - ps[r2][c1 - 1] + ps[r1 - 1][c1 - 1]
out.append(str(ans))
print('\n'.join(out))
solve_2d_prefix()
3. 최대 부분 직사각형 합 (2D Kadane)
행의 시작 인덱스 $r_1$과 끝 인덱스 $r_2$를 모든 쌍으로 고정하고, 각 열의 행 합을 압축한 1차원 배열에 카데인 알고리즘을 적용합니다. 총 시간 복잡도는 $O(N^2 M)$입니다.
# 8075번: 최대 부분 직사각형 합 — 2D Kadane
import sys
input = sys.stdin.readline
def solve_max_rect():
n, m = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(n)]
max_sum = float('-inf')
for r1 in range(n):
col_sum = [0] * m
for r2 in range(r1, n):
for c in range(m):
col_sum[c] += grid[r2][c]
# Kadane's on col_sum
cur = 0
for v in col_sum:
cur += v
max_sum = max(max_sum, cur)
if cur < 0:
cur = 0
print(max_sum)
solve_max_rect()
4. 분할 정복 DP 최적화 (Divide and Conquer DP)
점화식 $dp[t][i] = \min_{j < i}(dp[t-1][j] + cost(j+1, i))$에서 최적 분할점 $opt[i]$가 단조 증가하는 성질(Concave/Convex SMAWK property)을 만족하면, 분할 정복으로 최적점 탐색 범위를 좁혀 $O(N \log N)$ 레이어 처리로 단축합니다.
# 8076번: K 그룹 최소 비용 분할 — DP + Divide & Conquer 최적화
import sys
input = sys.stdin.readline
def solve_dcdc():
n, k = map(int, input().split())
costs = list(map(int, input().split()))
pre = [0] * (n + 1)
for i in range(n):
pre[i + 1] = pre[i] + costs[i]
def range_cost(l, r): # cost of segment (l+1..r), 0-indexed prefix
return pre[r] - pre[l]
INF = float('inf')
# prev[i]: min cost to split first i elements into t-1 groups
prev = [INF] * (n + 1)
prev[0] = 0
for i in range(1, n + 1):
prev[i] = pre[i] # 1 group: all prefix sum
for t in range(2, k + 1):
curr = [INF] * (n + 1)
curr[0] = 0
def dc(lo, hi, opt_lo, opt_hi):
if lo > hi:
return
mid = (lo + hi) // 2
best = INF
opt = opt_lo
for j in range(opt_lo, min(opt_hi, mid - 1) + 1):
if prev[j] == INF:
continue
c = prev[j] + range_cost(j, mid)
if c < best:
best = c
opt = j
curr[mid] = best
dc(lo, mid - 1, opt_lo, opt)
dc(mid + 1, hi, opt, opt_hi)
dc(t, n, t - 1, n - 1)
prev = curr
print(prev[n] if prev[n] != INF else 0)
solve_dcdc()
자주 하는 실수 & 오류 예방
-
Mo's 포인터 이동 순서: 확장(add)은 포인터를 이동한 뒤 해당 위치의 원소를 추가하고, 축소(remove)는 해당 위치의 원소를 제거한 뒤 포인터를 이동해야 합니다. 순서가 바뀌면 구간 경계 원소가 누락되거나 중복 처리됩니다.
-
2D 누적 합 포함-배제 부호 착오: $P[r_2][c_2] - P[r_1-1][c_2] - P[r_2][c_1-1] + P[r_1-1][c_1-1]$에서 두 번 빼진 모서리 $P[r_1-1][c_1-1]$을 다시 더하는 것을 잊지 마십시오.
-
2D 카데인의 최댓값 초기화: 격자 전체가 음수일 수 있으므로,
max_sum을
0이 아닌
float('-inf')로 초기화해야 합니다.
-
분할 정복 DP 단조성 확인: 분할 정복 DP 최적화는 최적 분할점이 단조 증가하는 경우에만 올바르게 동작합니다. 비용 함수가 Concave/Convex SMAWK 조건을 만족하는지 확인 후 적용합니다.
핵심 정리
| 알고리즘 |
시간 복잡도 |
공간 복잡도 |
주요 활용 |
| Mo's Algorithm |
$O((N+Q)\sqrt{N})$ |
$O(N)$ |
오프라인 구간 통계 쿼리 (Distinct Count, Mode 등) |
| 2D Prefix Sum |
$O(NM)$ 전처리 + $O(1)$ 쿼리 |
$O(NM)$ |
부분 직사각형 합, 2D 범위 집계 |
| 2D Kadane |
$O(N^2 M)$ |
$O(M)$ |
최대 부분 직사각형 합 |
| D&C DP 최적화 |
$O(KN \log N)$ |
$O(N)$ |
최적 분할점 단조 증가 DP (Optimal BST, K-way merge 비용) |
실습 문제
| 문제 번호 |
문제 제목 |
출처 |
난이도 |
핵심 알고리즘 |
| 8073 |
구간 서로 다른 수 |
CSES |
어려움 |
Mo's Algorithm (√N 블록 정렬 오프라인 쿼리) |
| 8074 |
2D 구간 합 쿼리 |
CSES |
보통 |
2차원 누적 합 (2D Prefix Sum) |
| 8075 |
최대 부분 직사각형 합 |
CSES |
어려움 |
2D 카데인(행 고정 후 1D Kadane 적용) |
| 8076 |
K 그룹 최소 비용 분할 |
BFStudy |
어려움 |
분할 정복 DP 최적화 (D&C DP Optimization) |