Ch 15. 고급 최적화 알고리즘 (Advanced Optimization)

Lesson 215. 고급 최적화 알고리즘

Advanced Optimization: Mo's Algorithm, 2D Prefix Sum, Max Subrectangle, D&C DP - Mo's Algorithm으로 구간 통계 쿼리를 $O((N+Q)\sqrt{N})$ 오프라인 처리 - 2차원 누적 합으로 임의 부분 직사각형 합을 $O(1)$에 계산 - 2D 카데인 알고리즘으로 최대 합 부분 직사각형 $O(N^2 M)$ 탐색 - 분할 정복 DP 최적화(D&C DP)로 $K$ 그룹 분할 비용을 $O(KN \log N)$ 산출

수업 목표 및 핵심 역량

- 쿼리를 √N 블록 단위로 정렬하고 포인터 이동으로 구간 통계를 갱신하는 Mo's Algorithm을 구현합니다. - 2차원 배열의 전처리 누적 합 배열을 구성하고 포함-배제 원리로 임의 구간 합을 산출합니다. - 행 고정 + 열 압축 후 1D Kadane을 반복 적용하여 최대 합 부분 직사각형을 탐색합니다. - 최적 분할점의 단조 증가 성질을 활용한 분할 정복 DP 최적화를 구현합니다.

Mo's Algorithm 핵심 구조

- 쿼리를 블록 기준으로 정렬 → 포인터 $l, r$ 이동으로 $O(1)$ 갱신

# 8073번: Mo's Algorithm 핵심 발췌
block = int(n ** 0.5)
queries.sort(key=lambda x: (x[0] // block, x[1] if ... else -x[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  # 현재 서로 다른 수의 개수

2D 누적 합 전처리 & 쿼리

- 구축: $P[i][j] = A[i][j] + P[i-1][j] + P[i][j-1] - P[i-1][j-1]$

# 8074번: 2D 구간 합 쿼리 발췌
for i in range(1, n + 1):
    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]

# 쿼리: 포함-배제
ans = ps[r2][c2] - ps[r1-1][c2] - ps[r2][c1-1] + ps[r1-1][c1-1]

최대 부분 직사각형 합 (2D Kadane)

- 행 범위 $(r_1, r_2)$ 고정 → 열 합 배열 → 카데인

# 8075번: 최대 부분 직사각형 합 발췌
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]
        # 1D Kadane on col_sum
        cur = 0
        for v in col_sum:
            cur += v
            max_sum = max(max_sum, cur)
            if cur < 0: cur = 0

분할 정복 DP 최적화

- 최적 분할점 단조 증가 → 분할 정복으로 탐색 범위 압축

# 8076번: D&C DP 최적화 핵심 발췌
def dc(lo, hi, opt_lo, opt_hi):
    if lo > hi: return
    mid = (lo + hi) // 2
    # opt_lo ~ min(opt_hi, mid-1) 범위에서 최적점 탐색
    best, opt = INF, opt_lo
    for j in range(opt_lo, min(opt_hi, mid - 1) + 1):
        c = prev[j] + range_cost(j, mid)
        if c < best: best, opt = c, j
    curr[mid] = best
    dc(lo, mid - 1, opt_lo, opt)
    dc(mid + 1, hi, opt, opt_hi)

오류 예방 및 안정성 체크

- **Mo's 포인터 순서:** 확장 시 이동 후 add, 축소 시 remove 후 이동 — 반드시 이 순서를 유지해야 경계 원소 처리가 정확합니다. - **2D 누적 합 부호:** 포함-배제에서 $+P[r_1-1][c_1-1]$ 항을 빠뜨리면 오답이 됩니다. - **2D 카데인 초기화:** 전체가 음수인 경우를 위해 max_sum = float('-inf')로 시작합니다. - **D&C DP 단조성 가정:** 비용 함수가 Quadrangle Inequality를 만족해야 이 최적화가 유효합니다.