분할 정복 알고리즘

분할 정복이란

분할 정복(Divide and Conquer)은 문제를 더 작은 동일 구조의 부분 문제로 분할하고, 재귀적으로 해결한 뒤 결합하는 알고리즘 패러다임입니다.

T(n) = aT(n/b) + f(n)

마스터 정리로 복잡도 분석:

• f(n) = O(n^(log_b a - ε)) → T(n) = O(n^log_b a)
• f(n) = Θ(n^log_b a) → T(n) = O(n^log_b a · log n)
• f(n) = Ω(n^(log_b a + ε)) → T(n) = O(f(n))

병합 정렬 (Merge Sort)

안정 정렬, O(N log N) 보장.

void merge(vector<int>& arr, int l, int m, int r) {
    vector<int> left(arr.begin() + l, arr.begin() + m + 1);
    vector<int> right(arr.begin() + m + 1, arr.begin() + r + 1);

    int i = 0, j = 0, k = l;
    while (i < (int)left.size() && j < (int)right.size())
        arr[k++] = (left[i] <= right[j]) ? left[i++] : right[j++];
    while (i < (int)left.size())  arr[k++] = left[i++];
    while (j < (int)right.size()) arr[k++] = right[j++];
}

void mergeSort(vector<int>& arr, int l, int r) {
    if (l >= r) return;
    int m = l + (r - l) / 2;
    mergeSort(arr, l, m);
    mergeSort(arr, m + 1, r);
    merge(arr, l, m, r);
}

역전 쌍 카운팅: merge 단계에서 right 원소가 먼저 선택될 때 left의 남은 원소 수만큼 역전 추가.

long long inversions = 0;

void merge(vector<int>& arr, int l, int m, int r) {
    // ... (위와 동일)
    while (i < left.size() && j < right.size()) {
        if (left[i] <= right[j]) {
            arr[k++] = left[i++];
        } else {
            inversions += left.size() - i;  // 역전 쌍 카운트
            arr[k++] = right[j++];
        }
    }
    // ...
}

퀵 정렬 (Quick Sort)

평균 O(N log N), 최악 O(N²). 캐시 효율이 좋아 실전에서 빠릅니다.

int partition(vector<int>& arr, int l, int r) {
    // 3-median pivot으로 최악 케이스 방지
    int m = l + (r - l) / 2;
    if (arr[l] > arr[m]) swap(arr[l], arr[m]);
    if (arr[l] > arr[r]) swap(arr[l], arr[r]);
    if (arr[m] > arr[r]) swap(arr[m], arr[r]);
    swap(arr[m], arr[r - 1]);
    int pivot = arr[r - 1];

    int i = l, j = r - 1;
    while (true) {
        while (arr[++i] < pivot);
        while (arr[--j] > pivot);
        if (i >= j) break;
        swap(arr[i], arr[j]);
    }
    swap(arr[i], arr[r - 1]);
    return i;
}

void quickSort(vector<int>& arr, int l, int r) {
    if (r - l < 10) {  // 작은 구간은 삽입 정렬
        for (int i = l + 1; i <= r; i++) {
            int key = arr[i], j = i - 1;
            while (j >= l && arr[j] > key) arr[j + 1] = arr[j--];
            arr[j + 1] = key;
        }
        return;
    }
    int p = partition(arr, l, r);
    quickSort(arr, l, p - 1);
    quickSort(arr, p + 1, r);
}

거듭제곱 (Fast Exponentiation)

O(log N)으로 a^n 계산.

long long power(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = result * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}

// 행렬 거듭제곱 (피보나치 O(log N))
using Matrix = vector<vector<long long>>;

Matrix multiply(const Matrix& A, const Matrix& B, long long mod) {
    int n = A.size();
    Matrix C(n, vector<long long>(n, 0));
    for (int i = 0; i < n; i++)
        for (int k = 0; k < n; k++)
            if (A[i][k])
                for (int j = 0; j < n; j++)
                    C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % mod;
    return C;
}

Matrix matpow(Matrix A, long long p, long long mod) {
    int n = A.size();
    Matrix R(n, vector<long long>(n, 0));
    for (int i = 0; i < n; i++) R[i][i] = 1;  // 단위 행렬
    while (p) {
        if (p & 1) R = multiply(R, A, mod);
        A = multiply(A, A, mod);
        p >>= 1;
    }
    return R;
}

최근접 점 쌍 (Closest Pair of Points)

O(N log N). 브루트포스 O(N²)보다 빠릅니다.

struct Point { double x, y; };

double dist(const Point& a, const Point& b) {
    return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
}

double closestPair(vector<Point>& pts, int l, int r) {
    if (r - l <= 3) {
        double d = 1e18;
        for (int i = l; i < r; i++)
            for (int j = i + 1; j < r; j++)
                d = min(d, dist(pts[i], pts[j]));
        sort(pts.begin() + l, pts.begin() + r,
             [](const Point& a, const Point& b){ return a.y < b.y; });
        return d;
    }

    int m = (l + r) / 2;
    double midX = pts[m].x;
    double d = min(closestPair(pts, l, m), closestPair(pts, m, r));

    // 중앙 띠 검사
    vector<Point> strip;
    for (int i = l; i < r; i++)
        if (abs(pts[i].x - midX) < d)
            strip.push_back(pts[i]);

    sort(strip.begin(), strip.end(),
         [](const Point& a, const Point& b){ return a.y < b.y; });

    for (int i = 0; i < (int)strip.size(); i++)
        for (int j = i + 1; j < (int)strip.size() && strip[j].y - strip[i].y < d; j++)
            d = min(d, dist(strip[i], strip[j]));

    return d;
}

카라추바 곱셈 (Karatsuba)

큰 수 곱셈 O(N^1.585).

// 두 큰 수를 벡터로 표현한 곱셈
vector<long long> karatsuba(vector<long long>& a, vector<long long>& b) {
    int n = a.size();
    if (n <= 32) {  // 기저: 브루트포스
        vector<long long> c(2 * n, 0);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                c[i + j] += a[i] * b[j];
        return c;
    }

    int half = n / 2;
    vector<long long> a0(a.begin(), a.begin() + half);
    vector<long long> a1(a.begin() + half, a.end());
    vector<long long> b0(b.begin(), b.begin() + half);
    vector<long long> b1(b.begin() + half, b.end());

    auto z0 = karatsuba(a0, b0);
    auto z2 = karatsuba(a1, b1);

    // (a0+a1)(b0+b1)
    vector<long long> a01(half), b01(half);
    for (int i = 0; i < half; i++) { a01[i] = a0[i]+a1[i]; b01[i] = b0[i]+b1[i]; }
    auto z1 = karatsuba(a01, b01);

    // z1 = z1 - z0 - z2
    for (int i = 0; i < (int)z1.size(); i++) {
        z1[i] -= (i < (int)z0.size() ? z0[i] : 0);
        z1[i] -= (i < (int)z2.size() ? z2[i] : 0);
    }

    vector<long long> result(2 * n, 0);
    for (int i = 0; i < (int)z0.size(); i++) result[i] += z0[i];
    for (int i = 0; i < (int)z1.size(); i++) result[i + half] += z1[i];
    for (int i = 0; i < (int)z2.size(); i++) result[i + n] += z2[i];
    return result;
}

분할 정복 최적화 DP

DP 점화식 dp[i][j] = min_{k<j}(dp[i-1][k] + cost(k+1,j))에서 최적 분할점이 단조 증가할 때 O(N² → N log N).

// Divide & Conquer DP Optimization
void solve(int layer, int lo, int hi, int optLo, int optHi,
           vector<vector<long long>>& dp,
           function<long long(int,int)> cost) {
    if (lo > hi) return;
    int mid = (lo + hi) / 2;
    int opt = optLo;
    long long best = LLONG_MAX;

    for (int k = optLo; k <= min(mid - 1, optHi); k++) {
        long long val = dp[layer - 1][k] + cost(k + 1, mid);
        if (val < best) { best = val; opt = k; }
    }
    dp[layer][mid] = best;

    solve(layer, lo, mid - 1, optLo, opt, dp, cost);
    solve(layer, mid + 1, hi, opt, optHi, dp, cost);
}

정리

• 분할 정복: 동일 구조 부분 문제로 재귀 → 마스터 정리로 복잡도 분석
• 병합 정렬 O(N log N) 안정 정렬, 역전 쌍 카운팅에 활용
• 행렬 거듭제곱으로 선형 점화식을 O(log N)에 계산
• 최근접 점 쌍: 중앙 띠 검사로 O(N log N) 달성
• D&C DP 최적화: 최적 분할점 단조성 활용