최종 수정일: 2026-11-04
Introduction to Algorithms, Cormen, Leiserson, Rivest, and Stein, Ch 4, 7, 9, 33
학습 목표:
- 분할 정복 패러다임(분할, 정복, 결합)을 설명하고 알고리즘에서 이를 식별할 수 있다
- 마스터 정리를 적용하여 분할 정복 점화식의 시간 복잡도를 결정할 수 있다
- 병합 정렬, 이진 탐색, 퀵 정렬, 선택 알고리즘을 단계별로 추적하고, 분할(PARTITION) 절차의 작동 방식과 퀵 정렬의 최선, 평균, 최악 경우를 분석할 수 있다
- 중앙값의 중앙값 알고리즘이 최악의 경우에도
$O(n)$ 선택을 보장하는 이유를 설명할 수 있다- 최근접 점 쌍 알고리즘을 적용하고 중간 띠(strip) 분석을 설명할 수 있다
- 분할 정복이 부적절한 경우(중복 부분 문제)를 인식하고 동적 프로그래밍을 대신 사용해야 할 때를 판단할 수 있다
섞여 있는 52장의 카드 덱을 정렬해야 하는 상황을 생각할 수 있다. 자연스러운 방법 중 하나는 덱을 절반으로 나누고, 각 절반을 정렬한 뒤, 두 절반을 합치는 것이다. 이것이 바로 분할 정복 전략이다. 큰 문제를 작은 문제들로 쪼개는 이 패러다임은 컴퓨터 과학에서 가장 강력한 아이디어 중 하나로 꼽힌다.
주어진 문제의 입력을 분할(Divide) 하고 각 부분을 정복(Conquer, 해결) 하는 알고리즘이다.
세 단계:
- 분할(Divide): 문제를 더 작은 부분 문제로 나눈다.
- 정복(Conquer): 각 부분 문제를 재귀적으로 해결한다.
- 결합(Combine): 부분 해를 합쳐 원래 문제의 해를 구한다.
핵심 용어:
- 부분 문제(Subproblem): 분할된 입력에 대해 정의된 문제이다.
- 부분 해(Subsolution): 부분 문제의 해이다.
- 부분 문제는 더 이상 나눌 수 없을 때까지(기저 사례, base case) 재귀적으로 분할된다.
핵심: 분할 정복의 핵심은 큰 문제를 작은 문제들로 쪼개면 각각이 쉬워진다는 아이디어이다. 단, 단순히 나누는 것만으로는 부족하고, 부분 해를 결합 하는 방법이 효율적이어야 전체 알고리즘이 효율적이 된다.
flowchart TD
P["문제"] -->|"분할(Divide)"| S1["부분문제1"]
P -->|"분할(Divide)"| S2["부분문제2"]
S1 -->|"정복"| T1["부분해1"]
S2 -->|"정복"| T2["부분해2"]
T1 -->|"결합(Combine)"| R["해"]
T2 -->|"결합(Combine)"| R
그림 1. 분할 정복의 분할, 정복, 결합 단계
예시: 입력 크기
분할할 때마다 부분 문제의 크기가 절반으로 줄어든다:
- 1회 분할 후: 각 크기
$= n/2$ - 2회 분할 후: 각 크기
$= n/2^2$ - ...
-
$k$ 회 분할 후: 각 크기$= n/2^k$
분할은 언제 멈추는가?
총 분할 횟수
[이산수학] 이산수학에서 다루는 로그 함수
$\log_2 n$ 은$2^k = n$ 을 만족하는 지수$k$ 이다. 크기$n$ 을 매번 절반으로 나누면$k$ 번 뒤의 크기가$n/2^k$ 이므로$\log_2 n$ 번 뒤에 크기가 1이 되며, 이것이 이진 탐색, 병합 정렬처럼 절반으로 나누는 알고리즘에$\log n$ 이 나타나는 근본적인 이유이다.
- 단순히 입력을 분할하는 것만으로는 대부분의 문제를 풀기에 충분하지 않다.
- 부분 문제를 정복 해야 한다. 즉, 부분 해를 구해야 한다.
- 부분 해를 결합(병합) 하여 더 큰 부분 문제의 해를 구성한다.
정복 방법은 구체적인 문제에 따라 달라진다.
참고: 결합의 구체적 예시. 병합 정렬에서 결합은 두 정렬된 리스트를 병합하는 것($O(n)$)이다. 이진 탐색에서 결합은 자명하다(결과를 그대로 반환). 최근접 점 쌍 문제에서 결합은 주의 깊은 띠(strip) 분석이 필요하다. 결합 단계가 알고리즘의 전체 복잡도를 결정하는 경우가 많다.
일반적인 점화식 형태:
-
$a$ = 분할 후 부분 문제의 수 -
$n/b$ = 각 부분 문제의 크기 -
$f(n)$ = 분할과 결합에 드는 비용
| 알고리즘 | ||
|---|---|---|
| 2 | 2 | 병합 정렬, 최근접 점 쌍 |
| 3 | 2 | 큰 정수 곱셈 (CLRS 4장의 내용으로, 이 정리본에서는 다루지 않음) |
| 7 | 2 | Strassen 행렬 곱셈 (CLRS 4장의 내용으로, 이 정리본에서는 다루지 않음) |
표 1. 부분 문제의 수 a와 크기 비율 b에 따른 분할 정복 알고리즘
핵심: 이 점화식에서
$a$ ,$b$ ,$f(n)$ 이 알고리즘의 시간 복잡도를 결정한다.$a$ 가 클수록 부분 문제가 많아져 비용이 증가하고,$b$ 가 클수록 부분 문제 크기가 빠르게 줄어든다.$f(n)$ 은 분할과 결합의 오버헤드이다.
재귀 트리의 각 레벨에서의 비용:
| 레벨 | 문제 크기 | 문제 수 | 비용 |
|---|---|---|---|
| 0 (루트) | 1 | ||
| 1 | |||
표 2. 재귀 트리의 레벨별 문제 크기, 문제 수, 비용
깊이:
그림 2. 마스터 정리의 재귀 트리
참고: 재귀 트리는 분할 정복 점화식을 시각적으로 이해하는 핵심 도구이다. 루트에서 리프까지 각 레벨의 비용을 모두 합하면 전체 시간 복잡도가 된다. 마스터 정리는 이 합산 결과를
$f(n)$ 과$n^{\log_b a}$ 의 비교로 간단히 판정하는 정리이다.
경우 1:
경우 2:
경우 3:
여기서
그림 3. T(n) = 3T(n/4) + cn²의 재귀 트리
참고: 경우 3의 정규 조건. 경우 3에는 정규 조건(regularity condition) 도 필요하다. 어떤 상수
$c < 1$ 과 충분히 큰 모든$n$ 에 대해$a \cdot f(n/b) \le c \cdot f(n)$ 이 성립해야 한다.
풀이 예시:
참고: 마스터 정리 적용 절차. 마스터 정리는 다음 순서로 적용한다.
- 점화식에서
$a$ ,$b$ ,$f(n)$ 을 식별한다.$n^{\log_b a}$ 를 계산한다.$f(n)$ 과$n^{\log_b a}$ 의 대소를 비교하여 경우 1, 2, 3 중 하나를 판정한다.- 해당 경우의 공식을 적용한다.
점화식으로 표현된 분할 정복 알고리즘의 시간 복잡도는 대부분 이 절차로 구할 수 있다.
| 점화식 | 설명 | 예시 |
|---|---|---|
| 2부분, 크기 불균등 | 퀵 정렬 | |
| 2부분, 1개만 필요, 절반 크기 | 이진 탐색 | |
| 2부분, 1개만 필요, 크기 불균등 | 선택 | |
| 크기가 1씩 감소 | 삽입 정렬, 피보나치 |
표 3. 기타 분할 정복 점화식의 패턴과 예
그림 4. 불균등 분할의 재귀 트리
핵심: 마스터 정리는
$T(n) = aT(n/b) + f(n)$ 형태에만 직접 적용할 수 있다. 퀵 정렬처럼 분할이 불균등하거나 삽입 정렬처럼 크기가 1씩만 줄어드는 경우에는 별도의 분석이 필요하다.
분할:
정복: 각 절반을 재귀적으로 정렬한다.
결합: 두 정렬된 절반을 하나의 정렬된 배열로 병합한다.
MERGE-SORT(A, p, r)
if p < r
q = floor((p + r) / 2)
MERGE-SORT(A, p, q) // 왼쪽 절반 정렬
MERGE-SORT(A, q+1, r) // 오른쪽 절반 정렬
MERGE(A, p, q, r) // 두 절반 병합
교재의 Figure 2.4는 병합 정렬이 정렬된 부분 배열을 아래에서 위로 병합하며 그 길이를 늘려 가는 과정을 보여 준다.
그림 5. 병합 정렬의 연산 트리
참고: 병합 정렬의 핵심은 3주차에서 다룬 MERGE 과정이다. 두 정렬된 배열을 하나로 합치려면, 각 배열의 첫 원소를 비교하여 작은 것을 결과 배열에 넣고 포인터를 전진시키는 방식을 반복한다. 이 과정이
$\Theta(n)$ 이다.
MERGE 절차:
MERGE(A, p, q, r)
n1 = q - p + 1 // 왼쪽 절반의 크기
n2 = r - q // 오른쪽 절반의 크기
배열 L[1..n1+1]과 R[1..n2+1]을 생성
for i = 1 to n1: L[i] = A[p + i - 1]
for j = 1 to n2: R[j] = A[q + j]
L[n1+1] = ∞ // 보초(sentinel)
R[n2+1] = ∞ // 보초(sentinel)
i = 1, j = 1
for k = p to r:
if L[i] <= R[j]:
A[k] = L[i]; i++
else:
A[k] = R[j]; j++
병합 추적: [27, 38]과 [3, 43]의 병합
| 단계 | 비교 | 동작 | 현재까지 결과 | i | j |
|---|---|---|---|---|---|
| 1 | L[1]=27 vs R[1]=3 | 3 < 27, R 선택 | [3] | 1 | 2 |
| 2 | L[1]=27 vs R[2]=43 | 27 < 43, L 선택 | [3, 27] | 2 | 2 |
| 3 | L[2]=38 vs R[2]=43 | 38 < 43, L 선택 | [3, 27, 38] | 3 | 2 |
| 4 | L[3]=∞ vs R[2]=43 | 43 < ∞, R 선택 | [3, 27, 38, 43] | 3 | 3 |
표 4. [27, 38]과 [3, 43]의 병합 추적
참고: 보초값(sentinel) ∞는 경계 검사의 필요성을 제거한다. 한 배열이 소진되면 그 배열의 다음 칸에 있는 ∞가 어떤 원소보다도 크므로, 나머지 배열의 원소들이 순서대로 복사된다.
점화식:
- 분할:
$O(1)$ (중간점만 계산) - 정복:
$2T(n/2)$ (절반에 대해 재귀 호출 두 번) - 결합:
$\Theta(n)$ (정렬된 두 배열을 병합)
마스터 정리 적용:
공간 복잡도:
참고: 병합 정렬은 항상
$\Theta(n \log n)$ 이다. 퀵 정렬과 달리 최악의 경우가 없다는 것이 장점이지만,$O(n)$ 의 추가 공간이 필요하다는 것이 단점이다.
원본: [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]
↘↙ ↘↙ ↘↙
[27, 38] [3, 43] [9, 82] [10]
↘ 병합 ↙ ↘ 병합 ↙
[3, 27, 38, 43] [9, 10, 82]
↘ 병합 ↙
[3, 9, 10, 27, 38, 43, 82]
그림 6. [38, 27, 43, 3, 9, 82, 10]에 대한 병합 정렬의 분할과 병합
아이디어: 정렬된 배열에서 탐색 공간을 반복적으로 절반으로 줄여가며 탐색한다.
BINARY-SEARCH(A, p, r, key)
if p > r
return NOT_FOUND
mid = floor((p + r) / 2)
if A[mid] == key
return mid
else if A[mid] > key
return BINARY-SEARCH(A, p, mid-1, key)
else
return BINARY-SEARCH(A, mid+1, r, key)
분할 정복 구조:
- 분할: key를 중간 원소와 비교
- 정복: 한쪽 절반에서만 재귀
- 결합: 자명 (결과를 그대로 반환)
핵심: 이진 탐색은 분할 정복의 특수한 형태로, 두 부분 문제 중 하나만 정복하면 된다. 이 때문에 점화식이
$T(n) = T(n/2) + O(1)$ 이 되어$\Theta(\log n)$ 이라는 매우 빠른 시간 복잡도를 달성한다.
점화식:
- 크기
$n/2$ 의 부분 문제 1개만 필요 - 각 레벨에서
$O(1)$ 작업 (비교 1회)
마스터 정리 적용:
정렬된 배열에서 key = 23 탐색:
인덱스: 0 1 2 3 4 5 6 7 8 9
값: [3, 8, 11, 15, 20, 23, 29, 31, 48, 65]
단계 1: p=0, r=9, mid=4 → A[4]=20 < 23 → 오른쪽 탐색
[ 23, 29, 31, 48, 65]
단계 2: p=5, r=9, mid=7 → A[7]=31 > 23 → 왼쪽 탐색
[23, 29]
단계 3: p=5, r=6, mid=5 → A[5]=23 == 23 → 인덱스 5에서 발견!
10개 원소에서 3번의 비교만으로 탐색을 마친다(최대 비교 횟수는
참고: 이진 탐색은 정렬된 배열에서만 사용할 수 있다. 정렬되지 않은 데이터에 적용하려면 먼저
$O(n \log n)$ 에 정렬해야 하므로, 탐색을 한 번만 할 경우에는 선형 탐색($O(n)$)이 오히려 더 효율적일 수 있다. 탐색이 여러 번 반복될 때 정렬 + 이진 탐색이 유리해진다.
분할: 배열을 피벗(pivot) 원소 기준으로 분할한다.
정복: 두 부분 배열을 재귀적으로 정렬한다.
결합: 자명하다. 제자리에서 분할하므로 두 부분 배열의 정렬이 끝나면 전체가 이미 정렬되어 있다.
QUICKSORT(A, p, r)
if p < r
q = PARTITION(A, p, r)
QUICKSORT(A, p, q-1) // 피벗 왼쪽 정렬
QUICKSORT(A, q+1, r) // 피벗 오른쪽 정렬
핵심: 병합 정렬과 퀵 정렬의 핵심 차이는 다음과 같다. 병합 정렬은 분할이 단순(절반 분할)하고 결합이 어렵다(병합). 반면 퀵 정렬은 분할이 어렵고(피벗 기반 분할) 결합이 자명하다.
마지막 원소를 피벗으로 선택한다. 다음 조건을 만족하도록 재배열한다:
- 피벗 이하(
$\le$ )인 원소는 왼쪽으로 - 피벗 초과(
$>$ )인 원소는 오른쪽으로
PARTITION(A, p, r)
pivot = A[r]
i = p - 1
for j = p to r - 1
if A[j] <= pivot
i = i + 1
swap A[i] and A[j]
swap A[i+1] and A[r]
return i + 1
피벗의 최종 인덱스를 반환한다. 교재의 Figure 7.2는 PARTITION이 부분 배열 A[j]가 피벗보다 큰 경우와 피벗 이하인 경우의 동작을 보여 준다.
그림 7. 분할 절차가 유지하는 네 영역
그림 8. 분할 절차의 반복 한 번에서 일어나는 두 경우
참고: 변수
i는 피벗 이하인 원소들이 모인 영역의 마지막 인덱스를 추적한다.j가 배열을 순회하면서 피벗 이하인 원소를 발견하면,i를 1 증가시키고A[i]와A[j]를 교환하여 해당 원소를 왼쪽 영역에 포함시킨다.
A = [31, 8, 48, 73, 11, 3, 20, 29, 65, 15]에서 pivot = 15로 분할:
pivot = A[9] = 15, i = -1
j=0: A[0]=31 > 15 → 건너뜀 [31, 8, 48, 73, 11, 3, 20, 29, 65, 15]
j=1: A[1]=8 <= 15 → i=0 → swap(A[0],A[1]) [ 8, 31, 48, 73, 11, 3, 20, 29, 65, 15]
j=2: A[2]=48 > 15 → 건너뜀 [ 8, 31, 48, 73, 11, 3, 20, 29, 65, 15]
j=3: A[3]=73 > 15 → 건너뜀 [ 8, 31, 48, 73, 11, 3, 20, 29, 65, 15]
j=4: A[4]=11 <= 15 → i=1 → swap(A[1],A[4]) [ 8, 11, 48, 73, 31, 3, 20, 29, 65, 15]
j=5: A[5]=3 <= 15 → i=2 → swap(A[2],A[5]) [ 8, 11, 3, 73, 31, 48, 20, 29, 65, 15]
j=6: A[6]=20 > 15 → 건너뜀 [ 8, 11, 3, 73, 31, 48, 20, 29, 65, 15]
j=7: A[7]=29 > 15 → 건너뜀 [ 8, 11, 3, 73, 31, 48, 20, 29, 65, 15]
j=8: A[8]=65 > 15 → 건너뜀 [ 8, 11, 3, 73, 31, 48, 20, 29, 65, 15]
최종: swap A[i+1]=A[3]과 A[r]=A[9]:
[ 8, 11, 3, 15, 31, 48, 20, 29, 65, 73]
^피벗 (인덱스 3)
결과: [8, 11, 3 | 15 | 31, 48, 20, 29, 65, 73]
최선/평균의 경우:
- 피벗이 배열을 매번 대략 절반으로 나누는 경우
$$T(n) = 2T(n/2) + \Theta(n) \implies T(n) = \Theta(n \log n)$$
최악의 경우:
- 피벗이 항상 가장 작거나 가장 큰 원소인 경우
- 분할 결과가 크기 0과
$n-1$ 로 나뉨$$T(n) = T(n-1) + \Theta(n) \implies T(n) = \Theta(n^2)$$
평균의 경우 (정식 분석):
공간:
참고: 최악의 경우가 생기는 입력. 마지막 원소를 피벗으로 쓰는 PARTITION에서는 이미 정렬된(또는 역순 정렬된) 배열이 매번 크기 0과
$n-1$ 의 분할을 만들어 최악의 경우가 된다. 이를 방지하기 위해 실무에서는 랜덤 피벗, 세 값의 중앙값(median-of-three) 등의 전략을 사용한다.
랜덤 분할(Randomized Partition):
문제: 정렬되지 않은 배열
두 가지 알고리즘:
- 랜덤 선택(Randomized Select): 평균
$\Theta(n)$ - 중앙값의 중앙값(Median of Medians, Linear Select): 최악
$\Theta(n)$
분할 정복 구조:
- 분할: 피벗으로 배열을 분할하고, 피벗의 순위를 확인
- 정복: 하나의 부분 배열에서만 재귀
- 결합: 자명
참고: 선택 문제는 배열 전체를 정렬하지 않고도
$i$ 번째 원소를 찾을 수 있는지를 묻는 문제이다. 정렬하면$O(n \log n)$ 이 걸리지만, 선택 알고리즘은$O(n)$ 으로 해결한다.
SELECT(A, p, r, i)
// A[p..r]에서 i번째로 작은 원소를 찾는다
if p == r
return A[p] // 원소가 하나뿐
q = PARTITION(A, p, r) // 피벗이 인덱스 q에 위치
k = q - p + 1 // 피벗은 A[p..r]에서 k번째로 작은 원소
if i < k
return SELECT(A, p, q-1, i) // 왼쪽에서 탐색
else if i == k
return A[q] // 피벗이 정답
else
return SELECT(A, q+1, r, i-k) // 오른쪽에서 탐색
-
평균 시간:
$\Theta(n)$ -
최악 시간:
$\Theta(n^2)$
핵심: 이 알고리즘은 퀵 정렬과 구조가 유사하지만, 한쪽 부분 배열에서만 재귀한다는 점이 핵심적인 차이이다. 퀵 정렬은 양쪽 모두 재귀하지만, 선택은 원하는 순위가 있는 쪽에서만 재귀하므로 더 빠르다.
입력: [31, 8, 48, 73, 11, 3, 20, 29, 65, 15] 찾기: i=2
단계 1: pivot=15로 PARTITION
결과: [8, 11, 3 | 15 | 31, 48, 20, 29, 65, 73]
피벗 위치 k=4 (4번째로 작은 원소)
i=2 < k=4 → 왼쪽 그룹 [8, 11, 3]에서 탐색
단계 2: [8, 11, 3]에서 pivot=3으로 PARTITION
결과: [3 | 8, 11]
피벗 위치 k=1
i=2 > k=1 → 오른쪽 그룹 [8, 11]에서 (2-1)=1번째로 작은 원소 탐색
단계 3: [8, 11]에서 pivot=11로 PARTITION
결과: [8 | 11]
피벗 위치 k=2
i=1 < k=2 → 왼쪽 그룹 [8]에서 탐색
단계 4: 원소가 하나뿐 → 8 반환
참고: 위 추적의 단계 2는 결과를 [3 | 8, 11]로 적었지만, 4.2절의 PARTITION을 [8, 11, 3]에 그대로 적용하면 피벗 3이 맨 앞 원소 8과 교환되어 [3 | 11, 8]이 된다. 이 경우 단계 3에서는 [11, 8]을 피벗 8로 분할하여 [8 | 11]과 k = 1을 얻고, i = 1 = k이므로 피벗 8을 바로 반환한다. 어느 쪽이든 답은 8이다.
입력: [31, 8, 48, 73, 11, 3, 20, 29, 65, 15] 찾기: i=7
단계 1: pivot=15로 PARTITION
결과: [8, 11, 3 | 15 | 31, 48, 20, 29, 65, 73]
왼쪽 그룹에 3개 원소, 피벗은 k=4
i=7 > k=4 → 오른쪽 그룹 [31, 48, 20, 29, 65, 73]에서
(7-4)=3번째로 작은 원소 탐색
단계 2: [31, 48, 20, 29, 65, 73]에서 재귀, 3번째로 작은 원소 찾기
pivot=73으로 PARTITION
결과: [31, 48, 20, 29, 65 | 73]
피벗 위치 k=6
i=3 < k=6 → 왼쪽 그룹 [31, 48, 20, 29, 65]에서 탐색
단계 3: [31, 48, 20, 29, 65]에서 재귀, 3번째로 작은 원소 찾기
pivot=65로 PARTITION
결과: [31, 48, 20, 29 | 65]
피벗 위치 k=5
i=3 < k=5 → 왼쪽 그룹 [31, 48, 20, 29]에서 탐색
단계 4: [31, 48, 20, 29]에서 재귀, 3번째로 작은 원소 찾기
pivot=29로 PARTITION
결과: [20 | 29 | 31, 48]
피벗 위치 k=2
i=3 > k=2 → 오른쪽 그룹 [31, 48]에서 (3-2)=1번째로 작은 원소 탐색
단계 5: [31, 48]에서 재귀, 1번째로 작은 원소 찾기
pivot=48로 PARTITION
결과: [31 | 48]
피벗 위치 k=2
i=1 < k=2 → 왼쪽 그룹 [31]에서 탐색
단계 6: 원소가 하나뿐 → 31 반환
정답: 7번째로 작은 원소는 31이다.
찾고자 하는 원소가 항상 더 큰 분할에 있다고 가정한다(평균 분석에서의 최악 시나리오).
랜덤 피벗은 확률 1/2로 원소들의 중간 50% (25번째 백분위수와 75번째 백분위수 사이)에 위치하며, 이때 더 큰 분할의 크기는 원래 크기의
전개하면:
[이산수학] 위 전개에는 이산수학에서 다루는 무한 등비급수의 합
$\sum_{k=0}^{\infty} r^k = \frac{1}{1-r}$ ($|r| < 1$ )이 쓰였다.$r = 3/4 < 1$ 이므로 급수가 수렴하여 계수가 상수$4c$ 가 되며, 이처럼 문제 크기가 매 단계 일정 비율로 줄어 비용이 기하급수적으로 감소하는 형태는 분할 정복 분석에서 자주 등장한다.
최악의 경우: 분할이 항상 크기 0과
최악의 경우에도 선형 시간을 보장할 수 있는가?
가능하다. 중앙값의 중앙값(Median-of-Medians) 알고리즘을 사용하면 된다.
LINEAR-SELECT(A, p, r, i)
// A[p..r]에서 i번째로 작은 원소를 찾는다
1. if |A| <= 5: 정렬 후 i번째 원소 반환
2. 원소들을 5개씩 그룹으로 나눈다 → ceil(n/5)개 그룹
3. 각 그룹의 중앙값을 구한다 → m_1, m_2, ..., m_{ceil(n/5)}
4. M = LINEAR-SELECT(medians, 1, ceil(n/5), ceil(n/10))
// 중앙값들의 중앙값을 재귀적으로 찾는다
5. A를 M 기준으로 분할한다
6. 적절한 쪽에서 재귀한다
핵심 통찰: M은 균형 잡힌 피벗임이 보장된다. 대략
참고: 5개씩 묶는 이유는, 3개씩 묶으면 점화식이
$T(n) = T(n/3) + T(2n/3) + \Theta(n)$ 이 되어 선형이 되지 않고, 7개 이상은 불필요하게 그룹 내 정렬 비용이 커지기 때문이다. 5가 선형 시간을 보장하는 가장 작은 그룹 크기이다.
단계 2: 37개 원소를 5개씩 그룹으로 나눈다:
그룹 1: [5, 1, 2, 9, 24] 그룹 5: [34, 6, 20, 32, 4]
그룹 2: [17, 33, 18, 16, 26] 그룹 6: [35, 15, 25, 11, 8]
그룹 3: [30, 13, 10, 21, 29] 그룹 7: [28, 23, 27, 22, 19]
그룹 4: [3, 36, 7, 37, 12] 그룹 8: [31, 14] (5개 미만)
단계 3: 각 그룹을 정렬하고 중앙값(3번째 원소)을 취한다:
그룹 1: [1,2,5,9,24] → 중앙값 = 5
그룹 2: [16,17,18,26,33] → 중앙값 = 18
그룹 3: [10,13,21,29,30] → 중앙값 = 21
그룹 4: [3,7,12,36,37] → 중앙값 = 12
그룹 5: [4,6,20,32,34] → 중앙값 = 20
그룹 6: [8,11,15,25,35] → 중앙값 = 15
그룹 7: [19,22,23,27,28] → 중앙값 = 23
그룹 8: [14,31] → 중앙값 = 14
단계 4:
이 8개 중앙값에 대해 LINEAR-SELECT를 재귀 호출하여
단계 5: 전체 배열을
- 왼쪽 그룹 (
$\le 15$ ): 15 이하의 원소 15개 - 오른쪽 그룹 (
$> 15$ ): 15 초과의 원소 22개
단계 6: 원하는 순위가 있는 쪽에서 재귀한다.
-
$\lceil n/5 \rceil$ 개의 중앙값 중 최소 절반은$\le M$ 이다 - 그러한 각 중앙값에 대해, 해당 그룹에서 최소 3개 원소가
$\le M$ 이다 - 따라서 최소
$3 \times \lceil n/10 \rceil \approx 3n/10$ 개의 원소가$\le M$ 이다 - 마찬가지로, 최소
$3n/10$ 개의 원소가$\ge M$ 이다 -
최악의 경우: 최대
$7n/10$ 개의 원소에 대해 재귀한다
교재의 Figure 9.1에서 각 열은 5개짜리 그룹이고, 흰 원은 각 그룹의 중앙값이며, 음영 영역은 중앙값의 중앙값
그림 9. 중앙값의 중앙값에 대한 균형 분석
점화식:
-
$T(n/5)$ : 중앙값들의 중앙값 찾기 (단계 4) -
$T(7n/10)$ : 더 큰 분할에서 재귀 (단계 6) -
$\Theta(n)$ : 그룹 나누기, 그룹 중앙값 구하기, 분할
참고: 선형 시간의 조건.
$1/5 + 7/10 = 9/10 < 1$ 이라는 조건이 선형 시간을 보장하는 핵심이다. 만약 이 합이 1 이상이면 기하급수적 감소가 성립하지 않아 선형 시간이 되지 않는다. 그룹 크기를 5로 정하는 이유와 이 알고리즘이 선형인 이유는 모두 이 조건으로 설명된다.
문제: 2차원 평면 위
완전 탐색(Brute-force) 접근:
- 모든 쌍의 거리를 계산:
$\binom{n}{2} = n(n-1)/2$ 개의 쌍 - 각 거리 계산:
$O(1)$ -
총:
$O(n^2)$
분할 정복으로 더 나은 해법을 구할 수 있는가?
전처리: 모든 점을 x좌표 기준으로 정렬한다. 시간은
분할: 점 집합
정복:
결합:
- 폭
$2d$ 의 중간 띠(strip) 에서$d$ 보다 가까운 쌍을 검사한다 - 존재한다면 이 쌍이
$CP_C$ 이다
반환:
핵심 통찰은 결합 단계에 있다:
←── d ──→←── d ──→
┌────────┬────────┐
│ │ │
│ S_L │ S_R │
│ │ │
│ · · │ · │
│ · │ · │
│ │ │
└────────┴────────┘
중간 띠 (폭 2d)
그림 10. 분할선 양쪽으로 폭 d씩인 중간 띠
- 분할선으로부터 거리
$d$ 이내의 점만 검사하면 된다. - 띠 안의 점들을 y좌표 기준으로 정렬한다.
- 각 점에 대해 y좌표 순서로 다음 몇 개의 점(최대 7개 이웃)만 비교하면 된다.
- 이로써 띠 검사가 점당
$O(1)$ 비교로 제한되어, 정렬 이후의 띠 검사는 전체$O(n)$ 이 된다.
핵심: 각 점에 대해 최대 7개만 비교하면 되는 이유가 이 알고리즘의 핵심 아이디어이다. 같은 쪽에 있는 점끼리는 서로 거리가
$d$ 이상이므로$d \times d$ 정사각형 하나에는 최대 4개, 폭$2d$ , 높이$d$ 인 직사각형에는 최대 8개의 점만 존재할 수 있다. 따라서 각 점에 대해 y좌표 순서로 다음 최대 7개의 점만 비교하면 충분하다.
CLOSEST-PAIR(S)
입력: S — x좌표 기준으로 정렬된 점들
출력: 최근접 점 쌍의 거리
1. if |S| <= 3: 모든 쌍의 거리를 계산하고 최솟값 반환
2. S를 x좌표 중앙값 기준으로 S_L과 S_R로 분할
3. CP_L = CLOSEST-PAIR(S_L)
4. CP_R = CLOSEST-PAIR(S_R)
5. d = min(dist(CP_L), dist(CP_R))
중간 띠(분할선으로부터 거리 d 이내)에서 최근접 점 쌍 CP_C를 찾는다
6. return min(CP_L, CP_C, CP_R) (거리 기준)
x좌표 정렬된 점: (2,·) (5,·) (10,·) (15,·) (20,·) | (25,·) (26,·) (28,·) (30,·) (37,·)
←──────── S_L ────────→ ←──────── S_R ────────→
단계 1: S_L에서 재귀 → CP_L (거리 = 10)
단계 2: S_R에서 재귀 → CP_R (거리 = 15)
단계 3: d = min(10, 15) = 10
단계 4: 중간 띠 = x ∈ [20-10, 25+10] = [10, 35] 범위의 점
띠 안의 점: (10,·) (15,·) (20,·) (25,·) (26,·) (28,·) (30,·)
단계 5: 띠를 y좌표로 정렬하고 인접 쌍을 검사
→ CP_C (거리 = 5)를 발견 (예시)
단계 6: return min(10, 5, 15) = 5 → CP_C가 최근접 점 쌍
점화식 분석:
| 행 | 비용 |
|---|---|
| 행 1 (기저 사례) | |
| 행 2 (분할) |
|
| 행 3~4 (재귀) | |
| 행 5 (띠 정렬 + 스캔) | |
| 행 6 (반환) |
표 5. CLOSEST-PAIR 의사코드의 행별 비용
마스터 정리 또는 직접 분석:
더 정교한 구현(y좌표 사전 정렬)을 사용하면
참고:
$O(n \log^2 n)$ 과$O(n \log n)$ 의 차이는 띠 내 점들을 매번 정렬하느냐($O(n \log n)$), 아니면 재귀 과정에서 y좌표 정렬을 유지하느냐의 차이이다.
앞 절들에서 분할 정복의 다양한 성공적 응용을 다루었다. 이 절에서는 이 패러다임이 실패하는 경우와 그 대안인 동적 프로그래밍을 사용해야 하는 경우를 다룬다.
분할 정복이 부적절한 경우: 부분 문제들의 전체 입력 크기가 분할 후에 크게 증가 하는 경우이다(예: 크기가 상수만큼만 줄어드는 부분 문제가 여러 개 생기는 경우).
피보나치:
graph TD
f6["F(6)"] --> f5["F(5)"]
f6 --> f4a["F(4)"]
f5 --> f4b["F(4)"]
f5 --> f3a["F(3)"]
f4a --> f3b["F(3)"]
f4a --> f2a["F(2)"]
f4b --> f3c["F(3)"]
f4b --> f2b["F(2)"]
f3a --> e1["..."]
f3b --> e2["..."]
그림 11. F(6)을 계산하는 피보나치 재귀 호출 트리의 일부
- 입력 크기:
$n$ - 부분 문제 입력 크기의 합:
$(n-1) + (n-2) = 2n - 3 > n$ -
$F(2)$ 는 5번,$F(3)$ 은 3번 계산된다. - 중복 계산이 지수적으로 늘어난다.
핵심: 분할 정복 vs 동적 프로그래밍의 핵심 구분점은 부분 문제의 중복 여부이다. 부분 문제가 겹치지 않으면(병합 정렬) 분할 정복, 겹치면(피보나치) 동적 프로그래밍이 적절하다.
분할 정복 대신 반복적 상향식(iterative bottom-up) 계산을 사용한다:
FIB-NUMBER(n)
F[0] = 0
F[1] = 1
for i = 2 to n
F[i] = F[i-1] + F[i-2]
return F[n]
시간:
교훈: 부분 문제가 크게 중복될 때는, 순진한 분할 정복보다 동적 프로그래밍(Dynamic Programming) (상향식 또는 메모이제이션)이 더 적절하다.
두 가지 핵심 고려사항:
-
입력 크기 증가: 부분 문제들의 크기가 상수만큼만 줄어들면서 전체 크기가 원래 입력 크기를 초과하면, 분할 정복은 지수적 폭발로 이어질 수 있다.
- 예시: 피보나치
-
결합 비용의 중요성: 단순히 입력을 분할하는 것만으로는 효율성이 보장되지 않는다.
- 부분 해의 결합 비용이 감당 가능해야 한다.
- 많은 기하 문제가 분할 정복에 적합한 이유는, 결합 단계가 문제 구조에 자연스럽게 맞기 때문이다.
| 개념 | 핵심 요약 |
|---|---|
| 분할 정복 | 분할, 정복, 결합의 세 단계로 문제를 푼다. |
| 마스터 정리 |
|
| 병합 정렬 | 점화식 |
| 이진 탐색 | 점화식 |
| 퀵 정렬 | 평균은 |
| 랜덤 선택 | 점화식 |
| 중앙값의 중앙값 선택 | 점화식 |
| 최근접 점 쌍 | 점화식 |
| 분할 정복이 부적절한 경우 | 부분 문제 크기의 합이 크게 증가하거나 부분 문제가 중복되면 분할 정복 대신 동적 프로그래밍을 사용한다. |
-
분할 정복: D&C의 세 단계는 무엇인가? 결합 단계가 자명한 예와 비용이 큰 예를 각각 하나씩 들어라.
정답
문제를 더 작은 부분 문제로 분할(Divide) 하고, 각 부분 문제를 재귀적으로 정복(Conquer) 한 뒤, 부분 해를 합쳐 원래 문제의 해로 결합(Combine) 한다. 이진 탐색과 퀵 정렬에서는 결합이 자명하다. 이진 탐색은 결과를 그대로 반환하고, 퀵 정렬은 제자리 분할 덕분에 배열이 이미 정렬되어 있다. 반면 병합 정렬에서는 결합에 비용이 든다. 정렬된 두 절반을 병합하는 데
$\Theta(n)$ 이 걸리며, 이것이 전체 점화식$T(n) = 2T(n/2) + \Theta(n)$ 의 핵심이다. -
마스터 정리: 다음에 마스터 정리를 적용하라: (a)
$T(n) = 2T(n/2) + n$ , (b)$T(n) = 4T(n/2) + n$ , (c)$T(n) = T(n/2) + n^2$ . 각각의 경우와 결과를 기술하라.정답
$f(n)$ 과$n^{\log_b a}$ 을 비교한다. (a)$a=2, b=2$ 이므로$n^{\log_2 2} = n$ 이고$f(n) = n$ 이다. 따라서 경우 2이고,$T(n) = \Theta(n \log n)$ (병합 정렬)이다. (b)$a=4, b=2$ 이므로$n^{\log_2 4} = n^2$ 이고$f(n) = n$ 은 다항식적으로 작다. 따라서 경우 1이고,$T(n) = \Theta(n^2)$ 이다. (c)$a=1, b=2$ 이므로$n^{\log_2 1} = 1$ 이고$f(n) = n^2$ 은 다항식적으로 크며, 정규 조건$f(n/2) = \frac{1}{4}f(n)$ 도 성립한다. 따라서 경우 3이고,$T(n) = \Theta(n^2)$ 이다. -
병합 정렬: 병합 정렬이 입력 순서에 관계없이 항상
$\Theta(n \log n)$ 인 이유는? 공간 복잡도는 얼마이며, 그 이유는?정답
병합 정렬은 원소 값과 무관하게 배열을 무조건 절반으로 나누고 병합한다. 분할 단계와 결합 단계 모두 입력에 의존하지 않는다. 재귀 트리의 깊이는
$\log_2 n$ 이고 각 레벨에서$\Theta(n)$ 의 병합 작업을 하므로, 최선, 평균, 최악 모두$T(n) = \Theta(n \log n)$ 이다. 공간 복잡도는$\Theta(n)$ 이다.MERGE절차가 두 절반을 복사할 보조 배열L,R을 필요로 하는데, 이는 퀵 정렬의 제자리 분할에 비해 큰 단점이다. -
퀵 정렬 최악: 마지막 원소를 피벗으로 선택할 때
$O(n^2)$ 이 되는 구체적인 입력 배열을 제시하라. 랜덤 피벗 선택은 어떻게 도움이 되는가?정답
[1, 2, 3, 4, 5]처럼 이미 정렬된 (또는 역순 정렬된) 배열이면 충분하다. 피벗5가 항상 최댓값이므로 분할 크기가$n-1$ 과$0$ 으로 나뉘고,$T(n) = T(n-1) + \Theta(n) = \Theta(n^2)$ 이 된다. 랜덤 분할(Randomized Partition) 은 임의 인덱스를 위치r로 옮긴 뒤 분할하므로 적대적 입력이 피벗 선택을 좌우하지 못한다. 따라서 입력 순서와 무관하게 기대 시간은$\Theta(n \log n)$ 이다. -
선택: 랜덤 선택의 기대 시간이
$O(n \log n)$ 이 아닌$O(n)$ 인 이유는? 먼저 정렬한 후 인덱싱하는 것과 어떻게 다른가?정답
선택은 분할 후 원하는 순위가 있는 한쪽만 재귀하지만 퀵 정렬은 양쪽 모두 재귀한다. 랜덤 피벗이면 더 큰 분할의 기대 크기가
$\le 3n/4$ 이므로 점화식$T(n) \le T(3n/4) + \Theta(n)$ 이 성립하고, 기하급수$\sum (3/4)^k$ 로 합산하면$4cn = \Theta(n)$ 이 된다. 정렬 후 인덱싱은 결국 묻지 않은 원소들의 순서까지 결정하는 낭비가 발생하므로$\Theta(n \log n)$ 이다. -
중앙값의 중앙값: 왜 특별히 5개씩 그룹으로 나누는가? 3개씩 나누면 어떻게 되는가?
정답
그룹 크기 5는 점화식
$T(n) = T(n/5) + T(7n/10) + \Theta(n)$ 을 만들며,$1/5 + 7/10 = 9/10 < 1$ 이므로 작업량이 기하급수적으로 감소해$\Theta(n)$ 으로 수렴한다. 3개씩 묶으면$T(n) = T(n/3) + T(2n/3) + \Theta(n)$ 이 되는데$1/3 + 2/3 = 1$ 이라 기하급수적 감소가 성립하지 않고 점화식이$\Theta(n \log n)$ 으로 풀려 선형 시간 보장을 잃는다. 5는$<1$ 조건을 만족하는 가장 작은 홀수 그룹 크기이다. -
최근접 점 쌍: 띠 검사를 점마다 최대 7개 이웃으로 제한할 수 있는 이유는? 이를 정당화하는 기하학적 논거는?
정답
폭
$2d$ 의 띠 안에서 같은 절반에 속한 점들은 서로 거리가$d$ 이상이다. 더 가까웠다면 재귀 호출에서 이미 발견했을 것이기 때문이다. 점$p$ 에 대해 거리$d$ 미만인 점은$p$ 아래쪽$2d \times d$ 직사각형 안에만 존재할 수 있다. 채우기 논증(packing argument)에 의해 이 직사각형의 왼쪽과 오른쪽$d \times d$ 정사각형에는 각각 최대 4개의 점만 들어갈 수 있으므로 직사각형 안의 점은 최대 8개이고, 띠를 y좌표로 정렬한 뒤$p$ 의 다음 7개 이웃만 비교하면 충분하다. -
D&C vs DP: 피보나치 수열을 D&C로 계산할 수 있다. 왜 이것이 나쁜 방법인가? 부분 문제 구조 측면에서 피보나치가 병합 정렬과 다른 점은?
정답
$F(n) = F(n-1) + F(n-2)$ 의 재귀는 중복 부분 문제(overlapping subproblems) 를 갖는다.F(n-2)는F(n-1)안에서도,F(n)의 직접 호출에서도 계산되며, 이런 중복이 지수적으로 누적되어$\Theta(\varphi^n)$ 이 된다. 병합 정렬의 두 절반은 서로 겹치지 않으므로 어떤 원소도 중복 계산되지 않는다. 부분 문제가 겹칠 때는 동적 프로그래밍(Dynamic Programming) 을 적용할 수 있다. 메모이제이션이나 상향식 테이블을 사용하면 각 값을 한 번만 계산해 피보나치 계산을$\Theta(n)$ 으로 줄인다.