분할 정복 (Divide and Conquer)¶

개요¶

분할 정복은 큰 문제를 작은 부분 문제로 나누고, 각각을 해결한 후 결합하는 알고리즘 설계 기법입니다.

목차¶

분할 정복 개념
병합 정렬
퀵 정렬
이진 탐색
거듭제곱
연습 문제

1. 분할 정복 개념¶

기본 단계¶

분할 정복 3단계:

1. 분할 (Divide)
   - 문제를 더 작은 부분 문제로 나눔

2. 정복 (Conquer)
   - 부분 문제를 재귀적으로 해결
   - 충분히 작으면 직접 해결

3. 결합 (Combine)
   - 부분 문제의 해를 합쳐 원래 문제의 해 구성

시각화¶

        [문제]
       /      \
   [부분1]  [부분2]
   /    \    /    \
 [a]   [b] [c]   [d]
   \    /    \    /
   [부분1]  [부분2]
       \      /
        [해답]

분할 정복 vs DP¶

┌────────────────┬─────────────────┬─────────────────┐
│                │ 분할 정복       │ DP              │
├────────────────┼─────────────────┼─────────────────┤
│ 부분 문제      │ 서로 독립       │ 중복 존재       │
│ 저장           │ 불필요          │ 메모이제이션    │
│ 예시           │ 병합정렬        │ 피보나치        │
└────────────────┴─────────────────┴─────────────────┘

2. 병합 정렬 (Merge Sort)¶

원리¶

1. 배열을 반으로 나눔
2. 각 부분을 재귀적으로 정렬
3. 정렬된 두 부분을 병합

[38, 27, 43, 3, 9, 82, 10]
           ↓ 분할
[38, 27, 43, 3]  [9, 82, 10]
      ↓              ↓
[38, 27] [43, 3] [9, 82] [10]
    ↓       ↓       ↓      ↓
[38][27] [43][3] [9][82]  [10]
    ↓       ↓       ↓      ↓
[27, 38] [3, 43] [9, 82] [10]
      ↓              ↓
[3, 27, 38, 43]  [9, 10, 82]
           ↓ 결합
[3, 9, 10, 27, 38, 43, 82]

구현¶

// C
void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    int L[n1], R[n2];

    for (int i = 0; i < n1; i++) L[i] = arr[left + i];
    for (int i = 0; i < n2; i++) R[i] = arr[mid + 1 + i];

    int i = 0, j = 0, k = left;

    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) arr[k++] = L[i++];
        else arr[k++] = R[j++];
    }

    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;

        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    result.extend(left[i:])
    result.extend(right[j:])
    return result

복잡도 분석¶

T(n) = 2T(n/2) + O(n)

분할: O(1)
정복: 2 × T(n/2)
결합: O(n)

마스터 정리:
a = 2, b = 2, f(n) = n
n^(log_b(a)) = n^1 = n
f(n) = Θ(n)

→ T(n) = Θ(n log n)

공간: O(n) - 임시 배열

3. 퀵 정렬 (Quick Sort)¶

원리¶

1. 피벗 선택
2. 피벗보다 작은 원소는 왼쪽, 큰 원소는 오른쪽
3. 각 부분을 재귀적으로 정렬

[5, 3, 8, 4, 2, 7, 1, 6], 피벗=5
           ↓ 파티션
[3, 4, 2, 1] [5] [8, 7, 6]
      ↓              ↓
[1, 2, 3, 4]    [6, 7, 8]
           ↓
[1, 2, 3, 4, 5, 6, 7, 8]

구현¶

// C++
int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;

    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            swap(arr[++i], arr[j]);
        }
    }

    swap(arr[i + 1], arr[high]);
    return i + 1;
}

void quickSort(vector<int>& arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);

        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

def quick_sort(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)
        quick_sort(arr, low, pi - 1)
        quick_sort(arr, pi + 1, high)

def partition(arr, low, high):
    pivot = arr[high]
    i = low - 1

    for j in range(low, high):
        if arr[j] < pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]

    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

복잡도 분석¶

평균: T(n) = 2T(n/2) + O(n) = O(n log n)
최악: T(n) = T(n-1) + O(n) = O(n²)
      (이미 정렬된 배열 + 첫/마지막 피벗)

공간: O(log n) - 재귀 스택

4. 이진 탐색 (Binary Search)¶

분할 정복 관점¶

문제: 정렬된 배열에서 target 찾기

분할: 중간값 기준으로 왼쪽/오른쪽 나눔
정복: target이 있는 쪽만 탐색
결합: 필요 없음 (찾으면 반환)

[1, 3, 5, 7, 9, 11, 13], target=9
           ↓
       [7] 중간값
      7 < 9
           ↓
    오른쪽 탐색: [9, 11, 13]
           ↓
       [11] 중간값
      11 > 9
           ↓
    왼쪽 탐색: [9]
           ↓
       찾음!

재귀 구현¶

// C++
int binarySearchRecursive(const vector<int>& arr, int left, int right, int target) {
    if (left > right) return -1;

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

    if (arr[mid] == target) return mid;
    if (arr[mid] > target) return binarySearchRecursive(arr, left, mid - 1, target);
    return binarySearchRecursive(arr, mid + 1, right, target);
}

def binary_search_recursive(arr, left, right, target):
    if left > right:
        return -1

    mid = (left + right) // 2

    if arr[mid] == target:
        return mid
    if arr[mid] > target:
        return binary_search_recursive(arr, left, mid - 1, target)
    return binary_search_recursive(arr, mid + 1, right, target)

5. 거듭제곱 (Exponentiation)¶

단순 방법 vs 분할 정복¶

a^n 계산

단순: a × a × a × ... × a (n번) → O(n)

분할 정복:
a^n = a^(n/2) × a^(n/2)        (n이 짝수)
a^n = a^(n/2) × a^(n/2) × a    (n이 홀수)

→ O(log n)

예: 2^10
= 2^5 × 2^5
= (2^2 × 2^2 × 2) × (2^2 × 2^2 × 2)
= ((2 × 2)^2 × 2)^2

구현¶

// C - 재귀
long long power(long long a, int n) {
    if (n == 0) return 1;
    if (n == 1) return a;

    long long half = power(a, n / 2);

    if (n % 2 == 0) {
        return half * half;
    } else {
        return half * half * a;
    }
}

// C - 반복 (비트 연산)
long long powerIterative(long long a, int n) {
    long long result = 1;

    while (n > 0) {
        if (n & 1) {  // n이 홀수
            result *= a;
        }
        a *= a;
        n >>= 1;
    }

    return result;
}

def power(a, n):
    if n == 0:
        return 1
    if n == 1:
        return a

    half = power(a, n // 2)

    if n % 2 == 0:
        return half * half
    else:
        return half * half * a

# 모듈러 거듭제곱 (큰 수)
def power_mod(a, n, mod):
    result = 1
    a %= mod

    while n > 0:
        if n & 1:
            result = (result * a) % mod
        a = (a * a) % mod
        n >>= 1

    return result

행렬 거듭제곱¶

피보나치를 O(log n)에 계산

[F(n+1)]   [1 1]^n   [F(1)]
[F(n)  ] = [1 0]   × [F(0)]

행렬 거듭제곱을 분할 정복으로!

def matrix_mult(A, B, mod=10**9+7):
    return [
        [(A[0][0]*B[0][0] + A[0][1]*B[1][0]) % mod,
         (A[0][0]*B[0][1] + A[0][1]*B[1][1]) % mod],
        [(A[1][0]*B[0][0] + A[1][1]*B[1][0]) % mod,
         (A[1][0]*B[0][1] + A[1][1]*B[1][1]) % mod]
    ]

def matrix_power(M, n, mod=10**9+7):
    if n == 1:
        return M

    if n % 2 == 0:
        half = matrix_power(M, n // 2, mod)
        return matrix_mult(half, half, mod)
    else:
        return matrix_mult(M, matrix_power(M, n - 1, mod), mod)

def fibonacci(n):
    if n <= 1:
        return n

    M = [[1, 1], [1, 0]]
    result = matrix_power(M, n)
    return result[1][0]

6. 연습 문제¶

문제 1: 배열의 역순 쌍 개수¶

i < j이고 arr[i] > arr[j]인 쌍의 개수

힌트

병합 정렬 과정에서 카운트

정답 코드

def count_inversions(arr):
    def merge_count(arr, temp, left, mid, right):
        i = left
        j = mid + 1
        k = left
        inv_count = 0

        while i <= mid and j <= right:
            if arr[i] <= arr[j]:
                temp[k] = arr[i]
                i += 1
            else:
                temp[k] = arr[j]
                inv_count += (mid - i + 1)  # 핵심!
                j += 1
            k += 1

        while i <= mid:
            temp[k] = arr[i]
            i += 1
            k += 1

        while j <= right:
            temp[k] = arr[j]
            j += 1
            k += 1

        for i in range(left, right + 1):
            arr[i] = temp[i]

        return inv_count

    def merge_sort_count(arr, temp, left, right):
        inv_count = 0
        if left < right:
            mid = (left + right) // 2
            inv_count += merge_sort_count(arr, temp, left, mid)
            inv_count += merge_sort_count(arr, temp, mid + 1, right)
            inv_count += merge_count(arr, temp, left, mid, right)
        return inv_count

    n = len(arr)
    temp = [0] * n
    return merge_sort_count(arr, temp, 0, n - 1)

난이도	문제	플랫폼	유형
⭐⭐	행렬 제곱	백준	행렬 거듭제곱
⭐⭐	피보나치 수 6	백준	행렬 거듭제곱
⭐⭐	K번째 수	백준	Quick Select
⭐⭐⭐	버블 소트	백준	역순 쌍
⭐⭐⭐	가장 가까운 두 점	백준	분할 정복

마스터 정리 (Master Theorem)¶

T(n) = aT(n/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))

예:
- 병합 정렬: T(n) = 2T(n/2) + n → O(n log n) [Case 2]
- 이진 탐색: T(n) = T(n/2) + 1 → O(log n) [Case 2]
- 거듭제곱: T(n) = T(n/2) + 1 → O(log n) [Case 2]

다음 단계¶

08_Backtracking.md - 백트래킹

참고 자료¶

Introduction to Algorithms (CLRS) - Chapter 4
Divide and Conquer

분할 정복 (Divide and Conquer)¶

개요¶

목차¶

1. 분할 정복 개념¶

기본 단계¶

시각화¶

분할 정복 vs DP¶

2. 병합 정렬 (Merge Sort)¶

원리¶

구현¶

복잡도 분석¶

3. 퀵 정렬 (Quick Sort)¶

원리¶

구현¶

복잡도 분석¶

4. 이진 탐색 (Binary Search)¶

분할 정복 관점¶

재귀 구현¶

5. 거듭제곱 (Exponentiation)¶

단순 방법 vs 분할 정복¶

구현¶

행렬 거듭제곱¶

6. 연습 문제¶

문제 1: 배열의 역순 쌍 개수¶

추천 문제¶

마스터 정리 (Master Theorem)¶

다음 단계¶

참고 자료¶