분할 정복

어떤 문제를 푸는가

문제를 크기가 작은 같은 형태의 부분 문제로 쪼개고, 각각을 재귀로 풀어,
그 답들을 합쳐 전체 답 을 만드는 설계 패러다임입니다. 병합 정렬, 거듭제곱
가속, 역전 카운팅, 가장 가까운 두 점 등 폭넓게 쓰입니다.

세 단계로 요약됩니다.

1. 분할(Divide) — 입력을 부분 문제로 나눈다.
2. 정복(Conquer) — 각 부분 문제를 재귀로 푼다 (충분히 작으면 직접).
3. 결합(Combine) — 부분해를 합쳐 전체해를 만든다.

복잡도 분석 — 점화식과 마스터 정리

분할 정복의 시간은 보통

$$ T(N) = a\,T(N/b) + f(N) $$

로 표현됩니다. \(a\)는 부분 문제 수, \(b\)는 크기 축소 비율, \(f(N)\)은 결합 비용.
마스터 정리로 자주 나오는 결과:

결합 비용 \(f(N)\)이 전체 복잡도를 좌우한다는 점이 분석의 핵심입니다.

예 1 — 빠른 거듭제곱

\(a^n\)을 \(n\)번 곱하지 않고 지수를 절반으로 줄여 계산합니다.

$$ a^n = \begin{cases} (a^{n/2})^2 & n \text{ 짝수} \\ a \cdot (a^{(n-1)/2})^2 & n \text{ 홀수} \end{cases} $$

지수가 매번 반으로 줄어 \(O(\log n)\). 모듈러 거듭제곱, 행렬 거듭제곱의 토대입니다.

예 2 — 역전 카운팅

병합 정렬을 하면서, 왼쪽 절반의 원소가 오른쪽 절반의 원소보다 클 때마다
"역전 쌍"을 셉니다. 병합 단계에서 한 번에 묶음으로 셀 수 있어 전체 \(O(N \log N)\)
에 모든 역전(앞이 뒤보다 큰 쌍)의 수를 구합니다. 단순 \(O(N^2)\)를 대체합니다.

왜 효율적인가

부분 문제를 독립적으로 풀어 중복 계산을 피하고, 결합 비용이 작을수록
재귀 트리의 각 레벨 비용이 작아집니다. 레벨 수는 \(\log_b N\)이므로, 레벨당
비용이 균형을 이루면 전체가 \(O(N \log N)\) 같은 효율로 떨어집니다.

DP와의 차이

DP도 부분 문제로 나누지만, 겹치는 부분 문제를 저장(메모이제이션) 합니다.
분할 정복은 보통 부분 문제가 겹치지 않을 때(서로 다른 구간) 적합합니다.
겹치면 DP, 안 겹치면 순수 분할 정복으로 보는 감각을 기르세요. 다음 강의에서
구현 예제를 봅니다.

빠른 거듭제곱 (C++)

모듈러 거듭제곱은 거의 모든 정수론 문제의 부품입니다.

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

ll power(ll a, ll n, ll mod) {
    ll res = 1 % mod;
    a %= mod;
    while (n > 0) {
        if (n & 1) res = res * a % mod;   // 홀수면 현재 a를 곱한다
        a = a * a % mod;                  // a를 제곱
        n >>= 1;                          // 지수 절반
    }
    return res;
}

재귀 대신 반복문으로 짠 형태입니다(이진 거듭제곱). 곱셈 도중 오버플로를 막기
위해 a * a가 long long 범위 안에 들도록 mod가 너무 크면 __int128을
씁니다.

역전 카운팅 (병합 정렬, C++)

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

ll inv = 0;
vector<int> a, tmp;

void mergesort(int l, int r) {            // [l, r)
    if (r - l <= 1) return;
    int m = (l + r) / 2;
    mergesort(l, m);
    mergesort(m, r);
    int i = l, j = m, k = l;
    while (i < m && j < r) {
        if (a[i] <= a[j]) tmp[k++] = a[i++];
        else {
            tmp[k++] = a[j++];
            inv += m - i;                 // a[i..m)이 모두 a[j]보다 크다
        }
    }
    while (i < m) tmp[k++] = a[i++];
    while (j < r) tmp[k++] = a[j++];
    for (int t = l; t < r; t++) a[t] = tmp[t];
}

inv += m - i; 한 줄이 핵심입니다. 오른쪽 원소 하나가 앞으로 끼어들 때,
왼쪽에 남은 모든 원소가 그보다 크므로 한 번에 묶어 셉니다.

파이썬 — 빠른 거듭제곱

def power(a, n, mod):
    res = 1 % mod
    a %= mod
    while n > 0:
        if n & 1:
            res = res * a % mod
        a = a * a % mod
        n >>= 1
    return res

# 파이썬 내장 pow(a, n, mod)가 동일 기능을 더 빠르게 제공한다

흔한 함정

• 재귀 종료 조건 — 구간 크기가 1 이하일 때 반드시 멈춰야 무한 재귀를 피합니다.
• 역전 카운트 자료형 — 역전 수는 최대 \(\binom{N}{2}\)로 매우 크므로 long long.
• 거듭제곱 오버플로 — a * a % mod에서 곱이 64비트를 넘으면 __int128.
• 구간 표기 일관성 — [l, r) 반열림이 off-by-one을 줄여 줍니다.

응용 패턴

• 거듭제곱 가속 — 모듈러 역원(페르마), 행렬 거듭제곱으로 점화식 가속.
• 카운팅 — 역전 수, 특정 조건 쌍 세기.
• 기하 — 가장 가까운 두 점(\(O(N \log N)\)), 평면 분할.
• 결정 단조성 최적화 — 분할 정복으로 DP 가속(상위 단원).

"쪼갠다 → 푼다 → 합친다"는 단순한 골격이지만, 결합 단계에서 무엇을 얼마나
싸게 합칠 수 있는가 가 모든 응용의 관건입니다.

출제 신호

분할 정복은 "절반으로 줄여도 같은 모양의 문제"가 보일 때 선택합니다.

• "\(N\)이 \(10^9{\sim}10^{18}\)처럼 터무니없이 큼" + 곱셈/점화 구조 —
  빠른 거듭제곱(수, 행렬) 신호. \(a^n \bmod p\), 피보나치 \(10^{18}\)항 등.
• 격자 크기가 \(2^k\)이고 "같은 패턴이 4(또는 9)분할로 반복" — Z-순서,
  쿼드트리 압축, 색종이류
• "두 구간의 답을 합칠 수 있는 통계" — 역전(inversion) 쌍 세기(병합 정렬
  변형), 가장 가까운 두 점, 히스토그램 최대 직사각형
• 일반형 판별: 문제를 반으로 잘랐을 때 (a) 왼쪽 답, (b) 오른쪽 답,
  © 경계를 걸치는 답을 빠르게 합칠 수 있으면 분할 정복입니다.

풀이 결정 절차

1. "절반"의 축을 정합니다 — 인덱스 절반, 지수 절반, 좌표 절반.
2. 결합 단계의 비용을 적고 마스터 정리로 검산합니다 —
   \(T(N) = 2T(N/2) + O(N)\)이면 \(O(N \log N)\),
   \(T(N) = T(N/2) + O(1)\)이면 \(O(\log N)\).
3. 경계를 걸치는 경우가 결합 단계에서 빠짐없이 처리되는지 확인합니다.
   분할 정복 오답의 대부분이 여기서 납니다.
4. 기저 사례(길이 1, 지수 0)를 명시합니다.

자주 하는 실수

• 거듭제곱에서 선형 재귀 — power(a, n-1) * a는 \(O(N)\)이라 의미가
  없습니다. 반드시 지수를 절반으로 줄여야 \(O(\log N)\)입니다.

def power(a, n, mod):
    if n == 0:
        return 1
    half = power(a, n // 2, mod)
    half = half * half % mod        # 곱할 때마다 즉시 mod
    if n % 2:
        half = half * a % mod
    return half

• 모듈러를 마지막에 한 번만 — 중간 곱이 오버플로(C++)하거나 파이썬에서도
  큰 수 곱으로 느려집니다. 곱셈마다 % mod가 원칙입니다. C++은
  (__int128) 또는 1LL * 캐스팅까지 챙기세요.
• 행렬 거듭제곱의 단위행렬 기저 — \(n = 0\)에서 영행렬을 돌려주면 전부
  무너집니다. 항등원이 무엇인지(수면 1, 행렬이면 \(I\)) 명확히.
• 중간점 무한 재귀 — mid = (lo + hi) / 2 후 [lo, mid], [mid, hi]로
  쪼개면 길이 2 구간에서 제자리걸음입니다. [lo, mid], [mid+1, hi]처럼
  구간이 반드시 줄어들게 자릅니다.
• 역전 쌍 세기에서 합치며 세지 않음 — 병합 단계에서 오른쪽 원소가 먼저
  나갈 때 "왼쪽에 남은 개수"를 더해야 하는데, 병합 후 따로 세려고 하면
  \(O(N^2)\)로 퇴화합니다. 카운트는 병합과 동시에.

연습 방법

사이드바 연습 목록에서 빠른 거듭제곱(수 → 행렬 → 피보나치 큰 항) 계열을
먼저 묶어 풀고, 다음으로 색종이/쿼드트리류 격자 분할, 마지막으로 역전 쌍
세기처럼 결합 단계에 아이디어가 들어가는 문제를 푸세요. 각 문제에서
\(T(N)\) 점화식을 적고 복잡도를 손으로 계산해 보는 것이 "분할 정복이 왜
빠른가"를 체화하는 가장 빠른 길입니다. 태그된 문제 3문제 이상 해결 시
마스터 처리되어 레이팅 CLASS 보너스에 반영됩니다.