분할 정복 알고리즘 완전 정복

개요

분할 정복은 문제를 더 작은 부분 문제로 나누고(Divide), 각각 해결한 후(Conquer), 결과를 결합(Merge)하는 알고리즘 패턴입니다. 재귀적 구조를 가지며, 마스터 정리로 시간 복잡도를 분석합니다.

---

1. 마스터 정리

T(n) = a·T(n/b) + f(n)

a: 부분 문제 수
b: 문제 크기 축소 비율
f(n): 분할/병합 비용

Case 1: f(n) = O(n^(log_b a - ε)) → T(n) = Θ(n^(log_b a))
Case 2: f(n) = Θ(n^(log_b a))   → T(n) = Θ(n^(log_b a) · log n)
Case 3: f(n) = Ω(n^(log_b a + ε)) → T(n) = Θ(f(n))

---

2. 병합 정렬 — O(N log N)

#include <vector>
#include <algorithm>

void MergeSort(std::vector<int>& arr, int left, int right) {
    if (left >= right) return;

    int mid = left + (right - left) / 2;
    MergeSort(arr, left, mid);      // 좌측 정렬
    MergeSort(arr, mid + 1, right); // 우측 정렬

    // 병합
    std::vector<int> temp;
    int i = left, j = mid + 1;

    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) temp.push_back(arr[i++]);
        else                   temp.push_back(arr[j++]);
    }
    while (i <= mid)   temp.push_back(arr[i++]);
    while (j <= right) temp.push_back(arr[j++]);

    for (int k = left; k <= right; k++)
        arr[k] = temp[k - left];
}

// T(n) = 2T(n/2) + O(n) → a=2, b=2, f(n)=O(n)
// log_2(2) = 1, f(n) = Θ(n^1) → Case 2 → O(n log n)

---

3. 역순 쌍 개수 (병합 정렬 응용)

// 배열에서 i < j이지만 arr[i] > arr[j]인 쌍의 수
long long CountInversions(std::vector<int>& arr, int left, int right) {
    if (left >= right) return 0;

    int mid = left + (right - left) / 2;
    long long count = 0;
    count += CountInversions(arr, left, mid);
    count += CountInversions(arr, mid + 1, right);

    // 병합 과정에서 역순 쌍 계산
    std::vector<int> temp;
    int i = left, j = mid + 1;

    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp.push_back(arr[i++]);
        } else {
            count += (mid - i + 1); // 오른쪽에서 선택 시 역순 쌍 수
            temp.push_back(arr[j++]);
        }
    }
    // ... 나머지 병합

    return count;
}

---

4. 빠른 거듭제곱 — O(log N)

// x^n을 O(log n)에 계산
long long Power(long long x, long long n, long long mod) {
    if (n == 0) return 1;

    long long half = Power(x, n / 2, mod);
    half = (half * half) % mod;

    if (n % 2 == 1)
        return (half * x) % mod;

    return half;
}

// T(n) = T(n/2) + O(1) → O(log n)

---

5. 최근접 점 쌍 — O(N log N)

#include <cmath>
#include <algorithm>

struct Point { double x, y; };

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

double ClosestPair(std::vector<Point>& pts, int left, int right) {
    if (right - left <= 3) {
        // 기저 케이스: 직접 비교
        double minD = 1e18;
        for (int i = left; i < right; i++)
            for (int j = i+1; j <= right; j++)
                minD = std::min(minD, Dist(pts[i], pts[j]));
        return minD;
    }

    int mid = left + (right - left) / 2;
    double midX = pts[mid].x;

    double d = std::min(
        ClosestPair(pts, left, mid),
        ClosestPair(pts, mid + 1, right));

    // 중간 띠(strip) 내 점 검사
    std::vector<Point> strip;
    for (int i = left; i <= right; i++)
        if (std::abs(pts[i].x - midX) < d)
            strip.push_back(pts[i]);

    // y 좌표 정렬 후 검사
    std::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 = std::min(d, Dist(strip[i], strip[j]));

    return d;
}

---

6. 이진 탐색 — O(log N)

// T(n) = T(n/2) + O(1) → O(log n)
int BinarySearch(const std::vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] == target) return mid;
        if (arr[mid] < target)  left = mid + 1;
        else                    right = mid - 1;
    }

    return -1; // 없음
}

// 정렬된 배열에서 첫 번째 true인 위치 찾기
int LowerBound(const std::vector<int>& arr, int target) {
    int left = 0, right = arr.size();
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] < target) left = mid + 1;
        else right = mid;
    }
    return left;
}

---

7. 게임 개발 활용

// 공간 분할 (쿼드 트리) — 충돌 감지 최적화
class QuadTree {
    Rect bounds;
    std::vector<GameObject*> objects;
    std::array<std::unique_ptr<QuadTree>, 4> children;

public:
    void Subdivide() {
        float halfW = bounds.width / 2, halfH = bounds.height / 2;
        children[0] = std::make_unique<QuadTree>(
            Rect{bounds.x,          bounds.y,          halfW, halfH});
        children[1] = std::make_unique<QuadTree>(
            Rect{bounds.x + halfW,  bounds.y,          halfW, halfH});
        // ... 나머지 두 사분면
    }

    std::vector<GameObject*> Query(const Rect& range) {
        if (!bounds.Intersects(range)) return {};

        std::vector<GameObject*> result;
        for (auto* obj : objects)
            if (range.Contains(obj->position))
                result.push_back(obj);

        if (children[0]) {
            for (int i = 0; i < 4; i++) {
                auto sub = children[i]->Query(range);
                result.insert(result.end(), sub.begin(), sub.end());
            }
        }
        return result;
    }
};

---

정리

알고리즘	분할	정복	병합	복잡도
병합 정렬	반으로	재귀 정렬	두 배열 병합	O(N log N)
이진 탐색	반으로	반쪽 탐색	없음	O(log N)
빠른 거듭제곱	n/2	재귀 계산	제곱	O(log N)
최근접 점 쌍	중앙 기준	각 절반	띠 검사	O(N log N)

참고 자료

• Introduction to Algorithms (CLRS) — Chapter 4