CS학습2026년 8월 23일

분할 정복: 문제를 쪼개고 합쳐서 복잡도를 줄이는 전략

분할 정복(Divide and Conquer)은 문제를 독립적인 하위 문제로 나누고, 각각을 재귀적으로 해결한 뒤 결과를 병합하는 알고리즘 설계 기법이다. 병합 정렬, 퀵 정렬, 이진 탐색 같은 핵심 알고리즘의 근간이며, 마스터 정리(Master Theorem)를 통해 시간 복잡도를 체계적으로 분석할 수 있다. 단순 반복문으로 풀기 어려운 문제를 O(n l

송민성6분 읽기

1. 개념

분할 정복(Divide and Conquer)은 큰 문제를 다음 세 단계로 해결하는 알고리즘 설계 패러다임이다.

분할(Divide): 원래 문제를 같은 형태의 더 작은 하위 문제로 나눈다.
정복(Conquer): 하위 문제가 충분히 작으면 직접 해결하고, 그렇지 않으면 재귀적으로 다시 분할한다.
결합(Combine): 하위 문제의 해를 합쳐서 원래 문제의 해를 만든다.

동적 프로그래밍(Dynamic Programming)과 다른 점은, 분할 정복은 하위 문제들이 서로 겹치지 않고 독립적이라고 가정한다는 것이다. 하위 문제가 중복되면 분할 정복은 같은 계산을 반복하게 되어 비효율적이며, 이 경우 메모이제이션(Memoization)을 도입한 동적 프로그래밍이 더 적합하다.

2. 왜 사용하는가

복잡도 개선: 예를 들어 정렬을 완전 탐색 방식으로 하면 O(n²)이 걸리지만, 병합 정렬(Merge Sort)로 분할 정복을 적용하면 O(n log n)으로 줄어든다.
병렬화 가능성: 하위 문제들이 독립적이므로 멀티코어나 분산 시스템에서 각 하위 문제를 동시에 처리할 수 있다.
문제 구조 단순화: 큰 입력을 다루는 로직을 작은 입력에 대한 로직으로 환원할 수 있어 증명과 구현이 단순해진다.

3. 동작 원리

분할 정복의 시간 복잡도는 재귀 관계식(recurrence relation)으로 표현된다. 일반적인 형태는 다음과 같다.

text

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

a: 하위 문제의 개수
n/b: 하위 문제의 크기 (원래 크기를 b로 나눈 값)
f(n): 분할과 결합에 드는 비용

이 재귀식을 마스터 정리(Master Theorem)로 분석하면 세 가지 경우로 나뉜다.

f(n) = O(n^c)이고 c < log_b(a)이면 T(n) = O(n^(log_b a))
f(n) = O(n^c)이고 c = log_b(a)이면 T(n) = O(n^c * log n)
f(n) = O(n^c)이고 c > log_b(a)이면 T(n) = O(f(n))

병합 정렬은 a=2, b=2, f(n)=O(n)이므로 c = log_2(2) = 1과 일치하는 두 번째 경우에 해당해 T(n) = O(n log n)이 나온다.

재귀가 종료되는 지점(base case)을 명확히 정의하는 것이 핵심이다. base case가 없거나 잘못 정의되면 무한 재귀에 빠져 스택 오버플로우(Stack Overflow)가 발생한다.

4. 코드 예제

병합 정렬 (Merge Sort)

python

from typing import List

def merge_sort(arr: List[int]) -> List[int]:
    # base case: 원소가 1개 이하면 이미 정렬된 상태
    if len(arr) <= 1:
        return arr

    # 분할(Divide): 배열을 절반으로 나눈다
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    # 결합(Combine): 정렬된 두 배열을 병합한다
    return merge(left, right)


def merge(left: List[int], right: List[int]) -> List[int]:
    result = []
    i, j = 0, 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


if __name__ == "__main__":
    data = [5, 2, 9, 1, 5, 6]
    print(merge_sort(data))  # [1, 2, 5, 5, 6, 9]

이진 탐색 (Binary Search)

python

from typing import List, Optional

def binary_search(arr: List[int], target: int, low: int = 0, high: Optional[int] = None) -> int:
    if high is None:
        high = len(arr) - 1

    # base case: 탐색 범위가 없으면 실패
    if low > high:
        return -1

    mid = (low + high) // 2

    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        # 오른쩡 절반만 재귀적으로 탐색
        return binary_search(arr, target, mid + 1, high)
    else:
        # 왼쪽 절반만 재귀적으로 탐색
        return binary_search(arr, target, low, mid - 1)


if __name__ == "__main__":
    sorted_data = [1, 3, 5, 7, 9, 11, 13]
    print(binary_search(sorted_data, 7))   # 3
    print(binary_search(sorted_data, 4))   # -1

최대 부분합 (Maximum Subarray) - 분할 정복 방식

python

from typing import List

def max_subarray(arr: List[int], low: int = 0, high: int = None) -> int:
    if high is None:
        high = len(arr) - 1

    # base case: 원소가 하나면 그 값이 최대 부분합
    if low == high:
        return arr[low]

    mid = (low + high) // 2

    left_max = max_subarray(arr, low, mid)
    right_max = max_subarray(arr, mid + 1, high)
    cross_max = max_crossing_sum(arr, low, mid, high)

    return max(left_max, right_max, cross_max)


def max_crossing_sum(arr: List[int], low: int, mid: int, high: int) -> int:
    left_sum, total, best_left = float("-inf"), 0, float("-inf")
    for i in range(mid, low - 1, -1):
        total += arr[i]
        best_left = max(best_left, total)

    right_sum, total, best_right = float("-inf"), 0, float("-inf")
    for i in range(mid + 1, high + 1):
        total += arr[i]
        best_right = max(best_right, total)

    return best_left + best_right


if __name__ == "__main__":
    data = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
    print(max_subarray(data))  # 6 (부분배열 [4, -1, 2, 1])

5. 시간 복잡도 또는 성능 특성

| 알고리즘 | 재귀 관계식 | 시간 복잡도 | 공간 복잡도 | |---|---|---|---| | 병합 정렬 | T(n) = 2T(n/2) + O(n) | O(n log n) | O(n) | | 퀵 정렬 (평균) | T(n) = 2T(n/2) + O(n) | O(n log n) | O(log n) (재귀 스택) | | 퀵 정렬 (최악) | T(n) = T(n-1) + O(n) | O(n²) | O(n) | | 이진 탐색 | T(n) = T(n/2) + O(1) | O(log n) | O(log n) (재귀) 또는 O(1) (반복) | | 최대 부분합 (분할 정복) | T(n) = 2T(n/2) + O(n) | O(n log n) | O(log n) |

퀵 정렬은 피벗(pivot) 선택이 항상 최소값이나 최대값으로 편향되면 하위 문제가 균등하게 나뉘지 않아 최악의 경우 O(n²)까지 나빠진다. 반면 병합 정렬은 항상 절반으로 나누기 때문에 최악의 경우에도 O(n log n)을 보장한다.

6. 실무 사용 사례

정렬 라이브러리: Python의 sorted()와 list.sort()는 팀소트(Timsort)를 쓰는데, 이는 병합 정렬과 삽입 정렬을 결합한 하이브리드 알고리즘이다.
대규모 데이터 병렬 처리: MapReduce 패턴은 분할(Map) 후 결합(Reduce)하는 구조로, 분할 정복의 아이디어를 분산 시스템에 적용한 것이다.
행렬 곱셈 최적화: 슈트라센 알고리즘(Strassen's Algorithm)은 분할 정복으로 행렬 곱셈을 O(n³)에서 O(n^2.807)로 개선한다.
최근접 점 쌍 문제(Closest Pair of Points): 좌표 평면에서 가장 가까운 두 점을 찾을 때 분할 정복을 쓰면 O(n log n)에 해결할 수 있다. 완전 탐색은 O(n²)이 걸린다.

7. 주의할 점

재귀 깊이 제한: 언어별로 재귀 호출 깊이 제한이 있다. Python은 기본적으로 sys.getrecursionlimit()이 1000으로 설정되어 있어, 입력 크기가 매우 크면 RecursionError가 발생할 수 있다. 이 경우 반복문 기반으로 바꾸거나 sys.setrecursionlimit()을 조정해야 한다.
하위 문제 중복 여부 확인: 하위 문제가 겹치는 문제(예: 피보나치 수열)에 분할 정복을 그대로 적용하면 지수 시간이 걸린다. 이런 경우는 메모이제이션이나 동적 프로그래밍으로 접근해야 한다.
결합 단계 비용 과소평가: 분할은 쉽지만 결합(Combine) 단계가 비싼 경우가 많다. 병합 정렬의 merge 함수처럼 결합 비용이 전체 복잡도를 결정하는 경우가 흔하다.
불필요한 메모리 복사: Python에서 arr[:mid]처럼 슬라이싱을 하면 매번 새 리스트를 생성해 O(n) 추가 공간과 시간이 든다. 인덱스 범위(low, high)만 넘기는 방식으로 바꾸면 이런 오버헤드를 줄일 수 있다.

8. 핵심 정리

분할 정복은 문제를 독립적인 하위 문제로 나누고, 재귀적으로 풀고, 결과를 합치는 3단계 전략이다.
마스터 정리를 이용해 T(n) = aT(n/b) + f(n) 형태의 재귀 관계식에서 시간 복잡도를 도출할 수 있다.
병합 정렬, 이진 탐색, 퀵 정렬, 최근접 점 쌍 문제 등이 대표적인 응용이다.
하위 문제가 겹치면 동적 프로그래밍을 고려해야 하고, 재귀 깊이와 결합 비용을 항상 점검해야 한다.