algo · 16

분할정복

병합정렬재귀분할정복

분할정복(divide and conquer)은 큰 문제를 같은 종류의 더 작은 문제로 나누고(분할), 작은 문제를 풀고(정복), 그 답을 합쳐서(결합) 원래 문제의 답을 만드는 알고리즘 설계 방식입니다. 작은 문제는 같은 방법을 재귀적으로 적용해 풀고, 더 나눌 수 없을 만큼 작아지면 바로 답을 내는 기저 사례에서 멈춥니다.

병합 정렬, 이진 탐색, 거듭제곱의 빠른 계산이 모두 이 방식입니다. 분할정복의 효율은 얼마나 잘 나누고 얼마나 싸게 합치느냐에 달려 있고, 시간은 점화식으로 계산합니다. 이 토픽에서는 병합 정렬이 쪼개졌다가 합쳐지는 과정, 지수를 절반씩 줄이는 거듭제곱, 점화식을 재귀 트리로 펼쳐 비용을 더하는 방법을 봅니다.

핵심 개념

분할 · 정복 · 결합

문제를 작게 나누고, 각 부분 문제를 재귀로 풀고, 부분 해를 합쳐 전체 해를 만듭니다. 세 단계 중 무엇이 어려운지는 문제마다 다릅니다.

핵심 개념

기저 사례

더 나눌 수 없을 만큼 작은 문제는 바로 답을 냅니다. 병합 정렬에서는 원소가 하나뿐인 조각이 이미 정렬된 상태라는 점이 기저 사례입니다.

핵심 개념

병합 정렬

배열을 절반으로 나누어 각각 정렬한 뒤, 정렬된 두 조각을 앞에서부터 비교하며 하나로 합칩니다. 나누기는 쉽고 합치기에 일이 몰려 있는 형태입니다.

핵심 개념

점화식

T(n) = 2T(n/2) + n처럼 문제 크기 n의 시간을 더 작은 크기의 시간과 나누고 합치는 비용으로 적은 식입니다. 병합 정렬의 시간이 이 식에서 나옵니다.

핵심 개념

재귀 트리

점화식을 호출 구조로 펼친 트리입니다. 단계마다 비용을 구해 모두 더하면 전체 시간이 나옵니다. 병합 정렬은 단계마다 n이고 단계가 log n개입니다.

핵심 개념

마스터 정리

T(n) = aT(n/b) + f(n) 꼴의 점화식을 풀어 (a ≥ 1, b > 1이고 f(n)이 세 경우 중 하나에 맞으면) 시간을 바로 알려 주는 정리입니다. 병합 정렬은 a = 2, b = 2, f(n) = n이라 Θ(n log n)이 됩니다.

병합 정렬은 O(n log n)입니다 — 배열을 절반씩 나누면 단계가 log n개이고, 단계마다 전체 원소를 한 번씩 합치므로 n입니다. 기본 병합 정렬은 입력과 상관없이 소요 시간의 차수가 같아서 최선·평균·최악이 모두 O(n log n)입니다.

추가 공간이 필요합니다 — 배열 병합 정렬은 합칠 때 임시 공간 O(n)이 필요합니다. 재귀 깊이는 log n입니다.

거듭제곱은 O(log n)입니다 — 지수를 절반으로 줄이면 부분 문제가 하나뿐이라 T(n) = T(n/2) + O(1)이 되고, 호출이 log n 단계만 쌓입니다.

나누는 것이 어려운지 합치는 것이 어려운지가 갈립니다 — 병합 정렬은 나누기가 쉽고 합치기가 일이고, 퀵 정렬은 나누기(분할)에 일이 몰려 있고 합치기가 필요 없습니다.

이 시각화에서 확인할 것 — "병합 정렬" 탭에서 배열이 한 개씩 쪼개졌다가 정렬된 조각으로 합쳐지는 모습을, "거듭제곱" 탭에서 지수가 절반씩 줄며 호출이 쌓이고 결과가 돌아오는 모습을, "비용 트리" 탭에서 단계마다 비용이 n으로 같아지는 모습을 STEP으로 확인하세요.

분할정복의 배경

병합 정렬은 1945년 존 폰 노이만(John von Neumann)이 고안한 것으로 알려져 있고, 컴퓨터를 위해 만들어진 초기의 정렬 알고리즘 중 하나입니다. 분할정복 방식은 이후 빠른 곱셈과 행렬 곱셈 같은 문제에서도 점근적 개선을 이끌었습니다. 1962년 카라추바(Karatsuba)는 큰 수의 곱셈을 세 번의 절반 크기 곱셈으로 줄여 n^(log2 3) ≈ n^1.585 시간에 하는 방법을 보였고, 1969년 슈트라센(Strassen)은 행렬 곱셈을 n^(log2 7) ≈ n^2.81 시간에 하는 방법을 보였습니다.

숫자로 확인하기

분할 — 배열 [38, 27, 43, 3, 9, 82, 10, 5]를 크기 4, 2, 1로 세 번 절반씩 나누면 한 개짜리 조각 8개가 됩니다. log2 8 = 3단계입니다.

결합 — 한 개짜리 8개를 합치면 [27, 38], [3, 43], [9, 82], [5, 10]이 되고(비교 4번), 다음에 [3, 27, 38, 43]과 [5, 9, 10, 82]가 되며(비교 6번), 마지막에 [3, 5, 9, 10, 27, 38, 43, 82]가 됩니다(비교 7번). 비교는 모두 17번입니다.

거듭제곱 — 2^13은 지수가 13, 6, 3, 1, 0으로 줄며 호출이 5단계 쌓이고 곱셈 7번으로 8192가 됩니다. 단순하게 곱하면 12번입니다.

비용 트리 — n = 8, T(1) = 1이고 합치는 비용을 n으로 두면 합치기 단계 3개가 각각 8이라 24이고 기저 사례 8을 더해 T(8) = 32입니다. 이는 n log2 n + n = 8 × 3 + 8과 같고, 실제 비교는 한쪽이 먼저 비면 n보다 적어 17번이었습니다.

코드 확인 — 파이썬과 자바 병합 정렬이 같은 결과와 같은 비교 횟수 17번을 냅니다. 파이썬 거듭제곱은 2^13 = 8192, 3^5 = 243, 2^0 = 1을 돌려줍니다.

자주 하는 오해

나누기만 하면 빨라진다 — 나누고 합치는 비용이 있고, 합치기가 비싸면 이득이 줄어듭니다. 예를 들어 합치는 비용이 n²이면 병합 정렬의 이점이 없습니다.

분할정복은 반드시 재귀로 구현한다 — 재귀가 자연스럽지만 반복문으로도 구현합니다. 작은 조각부터 크기를 두 배씩 키워 합치는 상향식 병합 정렬이 그 예입니다.

병합 정렬은 제자리 정렬이다 — 배열 병합 정렬은 합치는 동안 임시 공간 O(n)이 필요합니다. 제자리로 만드는 방법은 있지만 복잡해서 일반 구현은 임시 공간을 씁니다.

병합 정렬도 입력에 따라 최악이 느려진다 — 퀵 정렬은 분할이 한쪽으로 치우치면 최악에 O(n²)이 되지만, 병합 정렬은 항상 거의 절반(크기 차이 1 이내)으로 나누므로 모든 입력에서 O(n log n)입니다.

분할정복과 동적 계획법은 같다 — 둘 다 부분 문제로 나누지만, 분할정복은 부분 문제가 서로 겹치지 않고 동적 계획법은 겹치는 부분 문제의 결과를 저장해 재사용합니다.

면접에서 이렇게 물어요

면접 질문

분할정복의 세 단계는?

분할(문제를 작게 나눔), 정복(부분 문제를 재귀로 풂), 결합(부분 해를 합침)입니다. 더 나눌 수 없으면 기저 사례로 바로 답을 냅니다.

면접 질문

병합 정렬의 시간·공간 복잡도는?

시간은 기본 병합 정렬에서 모든 경우에 O(n log n)이고 공간은 임시 배열 때문에 O(n)입니다. 절반씩 나누는 단계가 log n개이고 단계마다 합치는 비용이 n이기 때문입니다.

면접 질문

분할정복과 동적 계획법의 차이는?

분할정복은 겹치지 않는 부분 문제를 풀어 합치고, 동적 계획법은 겹치는 부분 문제의 결과를 저장해 같은 계산을 반복하지 않습니다. 부분 문제가 겹치는지가 기준입니다.

면접 질문

x^n을 어떻게 빠르게 계산하나요?

x^n = x^⌊n/2⌋ × x^⌊n/2⌋로 지수를 절반씩 줄이고, n이 홀수이면 x를 한 번 더 곱합니다. 곱셈이 O(log n)번 필요합니다.

실제 시스템에서는

표준 라이브러리 정렬 — 파이썬의 sort는 병합 정렬에 삽입 정렬을 섞은 Timsort를 쓰고, 자바의 객체 배열 정렬도 병합 정렬 계열의 안정 정렬을 씁니다.

이진 탐색 — 정렬된 범위를 절반으로 줄여 한쪽만 푸는 분할정복이라 T(n) = T(n/2) + 1, 곧 O(log n)입니다.

빠른 푸리에 변환 — 쿨리(Cooley)와 튜키(Tukey)가 1965년 발표한 FFT는 크기 n의 변환을 더 작은 변환들로 나누어 푸는 분할정복이고, 기수-2(n이 2의 거듭제곱)에서는 짝수·홀수 번째 입력으로 나누어 O(n log n)에 계산합니다.

함께 보면 좋은 토픽

정렬 알고리즘 비교 — 병합 정렬과 퀵 정렬 등의 성능과 특징을 봅니다.

이진 탐색 — 한쪽만 푸는 분할정복의 대표 예를 봅니다.

DP 기초 — 겹치는 부분 문제를 저장해 푸는 방식과 비교합니다.

시간 복잡도 — O(n log n)과 O(log n)의 의미를 봅니다.

참고 자료

교재 — Cormen, Leiserson, Rivest, Stein, "Introduction to Algorithms", 3rd ed., Chapter 2.3 Designing algorithms, Chapter 4 Divide-and-Conquer

교재 — Knuth, D. E., "The Art of Computer Programming, Volume 3: Sorting and Searching", 2nd ed., Section 5.2.4

논문 — Cooley, J. W. and Tukey, J. W., "An algorithm for the machine calculation of complex Fourier series", Mathematics of Computation 19(90), 1965

논문 — Strassen, V., "Gaussian elimination is not optimal", Numerische Mathematik 13, 1969

논문 — Knuth, D. E., "Von Neumann's first computer program", ACM Computing Surveys 2(4), 1970

공식 문서 — Python Sorting Techniques

소스 문서 — CPython listsort.txt (Timsort 설명)

공식 문서 — Java Arrays

Python — 병합 정렬

count = [0]                                       # 비교 횟수

def merge_sort(a):
    if len(a) <= 1:                              # 기저 사례: 이미 정렬됨
        return a
    mid = len(a) // 2
    left = merge_sort(a[:mid])                    # 분할 + 정복
    right = merge_sort(a[mid:])
    return merge(left, right)                    # 결합

def merge(left, right):
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        count[0] += 1
        if left[i] <= right[j]:
            out.append(left[i])
            i += 1
        else:
            out.append(right[j])
            j += 1
    return out + left[i:] + right[j:]          # 남은 조각을 이어 붙인다

print(merge_sort([38, 27, 43, 3, 9, 82, 10, 5]), count[0])
# [3, 5, 9, 10, 27, 38, 43, 82] 17

분할정복은 세 단계입니다. 문제를 더 작은 같은 문제로 나누고(분할), 각 부분을 재귀로 풀고(정복), 부분의 답을 합쳐 전체의 답을 만듭니다(결합). 병합 정렬에서 분할은 배열을 절반으로 가르는 일이고, 정복은 재귀 호출이며, 결합이 정렬된 두 조각을 하나로 합치는 merge 함수입니다. 길이가 1 이하인 조각은 이미 정렬된 상태라 재귀를 멈추는 기저 사례가 됩니다. merge는 두 조각의 맨 앞 원소를 비교해 작은 쪽을 꺼내므로 두 조각 길이의 합만큼의 시간이 듭니다. 시각화의 8개 원소 배열에서는 합치기 3단계에 비교가 4번, 6번, 7번 들어 모두 17번이고, 전체 시간은 O(n log n)입니다. 합치기에 임시 배열이 필요해서 추가 공간은 O(n)입니다. 같은 값이 있을 때 left[i] <= right[j]처럼 왼쪽을 먼저 꺼내면 원래 순서가 유지되는 안정 정렬이 됩니다. 시각화의 병합 정렬 탭이 보여 주는 과정과 같습니다.

Python — 분할정복 거듭제곱

def power(x, n):
    if n == 0:                                    # 기저 사례
        return 1
    half = power(x, n // 2)                    # 지수를 절반으로
    return half * half * x if n % 2 else half * half

print(power(2, 13), power(3, 5), power(2, 0))   # 8192 243 1

def power_iter(x, n):                           # 같은 아이디어를 반복문으로
    result = 1
    while n:
        if n & 1:
            result *= x
        x *= x
        n >>= 1
    return result

print(power_iter(2, 13))                  # 8192

x^n을 x를 n번 곱해서 구하면 곱셈이 n - 1번 필요하지만, x^n = x^⌊n/2⌋ × x^⌊n/2⌋로 지수를 절반씩 줄이면 호출이 log n 단계만 쌓입니다. n이 홀수이면 x를 한 번 더 곱합니다. 2^13은 호출이 13, 6, 3, 1, 0의 다섯 단계로 쌓이고 곱셈을 7번 해서 8192가 됩니다(단순하게 곱하면 12번). 부분 문제가 하나뿐이라 결합 비용이 상수이고 점화식이 T(n) = T(n/2) + O(1)이 되어 O(log n)입니다. 아래의 반복문 버전은 같은 아이디어를 지수의 비트를 아래부터 읽는 방식으로 옮긴 것이고, 재귀 깊이 없이 추가 변수 O(1)개로 계산합니다. 시각화의 거듭제곱 탭이 보여 주는 호출 쌓임과 같습니다.

Java — 병합 정렬

static int[] mergeSort(int[] a) {
    if (a.length <= 1) return a;
    int mid = a.length / 2;
    int[] left = mergeSort(Arrays.copyOfRange(a, 0, mid));
    int[] right = mergeSort(Arrays.copyOfRange(a, mid, a.length));
    int[] out = new int[a.length];
    int i = 0, j = 0, k = 0;
    while (i < left.length && j < right.length) {
        out[k++] = left[i] <= right[j] ? left[i++] : right[j++];
    }
    while (i < left.length) out[k++] = left[i++];
    while (j < right.length) out[k++] = right[j++];
    return out;
}

// mergeSort(new int[]{38, 27, 43, 3, 9, 82, 10, 5}) → [3, 5, 9, 10, 27, 38, 43, 82]

자바 버전도 같은 구조입니다. 배열을 절반으로 복사해 재귀로 정렬한 뒤 앞에서부터 비교하며 합치고, 한쪽이 먼저 끝나면 남은 쪽을 그대로 이어 붙입니다. 비교 횟수는 파이썬 예와 같이 17번입니다. 분할정복이 항상 빠른 것은 아닙니다. 조각을 나누고 합치는 비용이 있고, 부분 문제가 서로 겹치면 같은 문제를 여러 번 푸는 낭비가 생깁니다. 그런 경우에는 결과를 저장해 두는 동적 계획법이 알맞습니다.

분할 정복의 세 단계를 순서대로 나열한 것은?

큰 문제를 쪼개고, 작은 문제를 풀고, 답을 합칩니다.

문제를 더 작은 부분 문제로 나누고(분할), 각 부분 문제를 재귀적으로 해결한 뒤(정복), 부분 해를 합쳐 원래 문제의 해를 만듭니다(결합).

병합 정렬(Merge Sort)의 시간 복잡도는?

절반씩 나누는 단계가 log n 번, 각 단계에서 합치는 비용이 n 입니다.

배열을 절반씩 나누면 log n 단계가 있고, 각 단계에서 전체 원소를 합치는 데 O(n)이 들기 때문에 전체 O(n log n)입니다.

x^n(거듭제곱)을 분할 정복으로 계산하면 곱셈 횟수는 대략?

x^n = x^(n/2) × x^(n/2) 로 지수를 절반씩 줄입니다.

x^n을 x^(n/2)를 제곱해서 구하고, n이 홀수면 x를 한 번 더 곱합니다. 지수가 절반씩 줄어들기 때문에 곱셈이 O(log n)번 필요합니다.