1. 분할정복(Divide-and-Conquer) 설계 전략
•
분할(Divide):
해결이 쉬운 작은 부분문제로 분할
•
정복(Conquer):
각 부분문제를 독립적으로 해결
•
통합(Combine):
(필요하다면) 부분 해를 결합하여 전체 해를 구성
•
이 과정은 하향식(top-down) 접근법
2. 이분검색(Binary Search) — 분할정복적 구현
2.1 알고리즘 구조
•
문제:
크기 n인 정렬된 배열 S에서 x의 위치를 찾음
•
전략:
◦
배열의 중간(mid) 원소와 x를 비교
◦
같으면 정답
◦
x < S[mid]면 왼쪽, x > S[mid]면 오른쪽 부분배열에서 탐색(재귀)
◦
이 과정을 반복
•
재귀 구현 예시:
cpp
CopyEdit
index location(index low, index high) {
if (low > high) return 0;
mid = (low + high) / 2;
if (x == S[mid]) return mid;
else if (x < S[mid]) return location(low, mid-1);
else return location(mid+1, high);
}
C++
복사
•
파라미터 최적화:
S, x, n 등 변하지 않는 값은 전역 변수로 두고
재귀에서는 index만 전달
•
꼬리 재귀(tail recursion):
모든 재귀호출이 함수 마지막에서만 발생 → 반복문 변환이 용이
반복 구현이 상수 배수만큼 빠르며 점근적 복잡도는 동일
2.2 최악 시간복잡도 분석
•
단위연산:
x와 S[mid]의 비교
•
점화식 (n이 2의 거듭제곱):W(n)=W(n/2)+1, W(1)=1
W(n)=W(n/2)+1, W(1)=1W(n) = W(n/2) + 1,\ W(1) = 1
•
반복대입법:W(n)=W(n/2)+1=W(n/4)+2=⋯=W(1)+log2n=1+log2n
W(n)=W(n/2)+1=W(n/4)+2=⋯=W(1)+log2n=1+log2nW(n) = W(n/2) + 1 = W(n/4) + 2 = \dots = W(1) + \log_2 n = 1 + \log_2 n
•
수학적 귀납법 증명:
1.
출발점: n=1 → W(1)=1=log₁+1
2.
가정: W(n)=log₂n+1
3.
단계: W(2n)=W(n)+1=log₂n+2=log₂2n+1
•
점근적 해:W(n)=log2n+1 ∈ Θ(logn)
W(n)=log2n+1 ∈ Θ(logn)W(n) = \log_2 n + 1\ \in\ \Theta(\log n)
•
n이 2의 거듭제곱이 아닌 경우에도 동일한 해
3. 합병정렬(Merge Sort)
3.1 알고리즘 구조
•
문제:
n개의 정수 S[1..n]을 비내림차순 정렬
•
알고리즘:
cpp
CopyEdit
void mergesort(int n, keytype S[]) {
int h = n/2, m = n-h;
keytype U[1..h], V[1..m];
if (n > 1) {
copy S[1]~S[h] to U[1]~U[h];
copy S[h+1]~S[n] to V[1]~V[m];
mergesort(h, U);
mergesort(m, V);
merge(h, m, U, V, S);
}
}
C++
복사
•
합병(merge):
두 정렬된 배열 U[1..h], V[1..m]을 하나의 정렬 배열 S[1..h+m]으로 합침
각 단계마다 U[i]와 V[j]를 비교해 작은 값을 S에 저장
한쪽 배열이 끝나면 남은 부분을 복사
3.2 합병(merge) 함수
•
코드:
cpp
CopyEdit
void merge(int h, int m, const keytype U[], const keytype V[], keytype S[]) {
index i=1, j=1, k=1;
while (i<=h && j<=m) {
if (U[i] < V[j]) { S[k]=U[i]; i++; }
else { S[k]=V[j]; j++; }
k++;
}
if (i > h) copy V[j]~V[m] to S[k]~S[h+m];
else copy U[i]~U[h] to S[k]~S[h+m];
}
C++
복사
•
최악 비교 횟수:
h + m – 1
(두 배열 중 한쪽이 모두 먼저 소진될 때)
3.3 합병정렬의 시간복잡도 분석
•
점화식 (n=2ᵏ):W(n)=2W(n/2)+n−1,W(1)=0
W(n)=2W(n/2)+n−1,W(1)=0W(n) = 2W(n/2) + n - 1,\quad W(1) = 0
•
반복대입법:W(n)=2W(n/2)+n−1=2kW(n/2k)+(n−20)+(n−21)+⋯+(n−2k−1)=nlog2n−(n−1)
W(n)=2W(n/2)+n−1=2kW(n/2k)+(n−20)+(n−21)+⋯+(n−2k−1)=nlog2n−(n−1)W(n) = 2W(n/2) + n - 1
= 2^k W(n/2^k) + (n - 2^0) + (n - 2^1) + \cdots + (n - 2^{k-1})
= n \log_2 n - (n-1)
•
수학적 귀납법으로 증명 가능
(연습문제)
•
점근적 해:W(n)∈Θ(nlogn)
W(n)∈Θ(nlogn)W(n) \in \Theta(n \log n)
•
n이 2의 거듭제곱이 아니더라도 점근적으로 동일
3.4 합병정렬의 공간복잡도
•
표준 mergesort:
◦
각 단계마다 U, V 추가 필요
◦
전체 추가 공간 합: n + n/2 + n/4 + ... = 2n = Θ(n)
◦
입력 S 외에 Θ(n) 추가 공간 사용
◦
제자리 정렬(in-place sort) 아님
3.5 공간 최적화 mergesort2
•
부분 배열을 따로 만들지 않고, S 자체에서 인덱스 구간 활용
•
임시 배열 U만 사용, 정렬된 결과를 S에 복사
•
전체 추가 공간 합: Θ(n)
•
표준 mergesort에 비해 추가 공간 감소, 여전히 in-place 정렬은 아님
4. 결론
•
분할정복은 하향식으로 문제를 재귀적으로 분할, 부분문제를 해결, 결합하여 전체 해를 도출
•
이분검색의 최악 시간복잡도는 Θ(log n)
•
합병정렬의 최악 시간복잡도는 Θ(n log n), 공간복잡도는 Θ(n)
•
mergesort의 공간복잡도는 개선할 수 있으나, 제자리정렬이 되지는 않음
Divide and Conquer#2
1. Quicksort (빠른 정렬)
1.1 개념 및 작동 원리
•
1962년 Tony Hoare에 의해 제안.
•
실제로 “가장 빠른” 정렬은 아니며, partition exchange sort가 더 정확한 명칭.
•
Pivot을 임의로 선택해 배열을 두 부분으로 분할.
◦
L: pivot보다 작은 원소들의 배열
◦
R: pivot보다 큰 원소들의 배열
•
각 부분배열에 대해 재귀적으로 quicksort 수행.
•
분할(Partition) 과정: Θ(n)
1.2 알고리즘 구조 (Pseudo code)
python
CopyEdit
QuickSort(A):
if len(A) <= 1: return
랜덤으로 x = A[i] (pivot) 선택
L = [x보다 작은 값들]
R = [x보다 큰 값들]
A = L + [x] + R
QuickSort(L)
QuickSort(R)
Python
복사
1.3 실제 코드
cpp
CopyEdit
void quicksort(index low, index high) {
index pivotpoint;
if (high > low) {
partition(low, high, pivotpoint);
quicksort(low, pivotpoint-1);
quicksort(pivotpoint+1, high);
}
}
C++
복사
•
partition 함수가 pivot 기준으로 배열을 두 부분으로 분할.
1.4 Partition (분할 알고리즘)
•
첫 항목을 pivot으로 설정.
•
pivot보다 작은 값을 앞으로 옮김(교환).
•
마지막에 pivot을 제자리에 위치시킴.
cpp
CopyEdit
void partition(index low, index high, index& pivotpoint) {
index i, j;
keytype pivotitem = S[low];
j = low;
for(i = low + 1; i <= high; i++) {
if (S[i] < pivotitem) {
j++;
exchange S[i] and S[j];
}
}
pivotpoint = j;
exchange S[low] and S[pivotpoint];
}
C++
복사
•
pivot은 항상 정렬 후 올바른 위치에 놓임.
2. Quicksort의 시간복잡도 분석
2.1 Partition 과정의 복잡도
•
비교 연산: n – 1회 (입력크기 n)
•
입력 배열과 무관하게 항상 동일
2.2 Quicksort의 최악 시간복잡도
•
입력이 이미 정렬된 경우(항상 한쪽 부분만 분할):W(n)=W(0)+W(n−1)+n−1
W(n)=W(0)+W(n−1)+n−1W(n) = W(0) + W(n-1) + n-1
•
반복:W(n)=W(n−1)+n−1=(n−1)+(n−2)+…+1=2n(n−1)
W(n)=W(n−1)+n−1=(n−1)+(n−2)+…+1=n(n−1)2W(n) = W(n-1) + n-1 = (n-1) + (n-2) + \ldots + 1 = \frac{n(n-1)}{2}
•
Θ(n2)\Theta(n^2)Θ(n2)
2.3 Quicksort의 평균 시간복잡도
•
pivot이 p번째로 정렬될 확률: 1/n1/n1/n
•
점화식:A(n)=n1p=1∑n[A(p−1)+A(n−p)]+n−1
A(n)=1n∑p=1n[A(p−1)+A(n−p)]+n−1A(n) = \frac{1}{n} \sum_{p=1}^{n} [A(p-1) + A(n-p)] + n-1
•
변형:A(n)=n2p=1∑nA(p−1)+n−1
A(n)=2n∑p=1nA(p−1)+n−1A(n) = \frac{2}{n} \sum_{p=1}^{n} A(p-1) + n-1
•
해:A(n)≈2(n+1)Hn−4n≈2(n+1)lnn
A(n)≈2(n+1)Hn−4n≈2(n+1)lnnA(n) \approx 2(n+1) H_n - 4n \approx 2(n+1) \ln n
(Hn: 조화수, ln n: 로그)
•
Θ(nlogn)\Theta(n \log n)Θ(nlogn)
2.4 Quicksort의 최선 시간복잡도
•
pivot이 항상 중간값일 때:B(n)=2B(n/2)+n−1
B(n)=2B(n/2)+n−1B(n) = 2B(n/2) + n - 1
•
반복대입:B(n)=nlogn−2n+1∈Θ(nlogn)
B(n)=nlogn−2n+1∈Θ(nlogn)B(n) = n \log n - 2n + 1 \in \Theta(n \log n)
2.5 정리
•
최악: Θ(n2)\Theta(n^2)Θ(n2)
•
평균/최선: Θ(nlogn)\Theta(n \log n)Θ(nlogn)
•
제자리 정렬(in-place)
3. 행렬 곱셈 (Matrix Multiplication)
3.1 표준 행렬곱셈 알고리즘
•
n×nn \times nn×n 행렬 A, B의 곱 C 계산
•
3중 루프 사용:
◦
총 곱셈 연산: Θ(n3)\Theta(n^3)Θ(n3)
•
2x2 행렬: 8번 곱셈, 4번 덧셈
3.2 쉬트라쎈(Strassen) 행렬 곱셈
•
2x2 행렬곱을 7번의 곱셈, 18번의 덧셈/뺄셈으로 계산
•
부분행렬(submatrix) 재귀 분할
•
n×nn \times nn×n 행렬에 대해:
◦
점화식:T(n)=7T(n/2)+O(n2)
T(n)=7T(n/2)+O(n2)T(n) = 7T(n/2) + O(n^2)
◦
Θ(nlog27)≈Θ(n2.81)\Theta(n^{\log_2 7}) \approx \Theta(n^{2.81})Θ(nlog27)≈Θ(n2.81)
3.3 표준 vs. 쉬트라쎈 시간복잡도
•
표준: Θ(n3)\Theta(n^3)Θ(n3)
•
쉬트라쎈: Θ(n2.81)\Theta(n^{2.81})Θ(n2.81)
•
Coppersmith-Winograd: Θ(n2.38)\Theta(n^{2.38})Θ(n2.38) (상수 커서 실제론 비효율적)
4. 임계값(Threshold)과 분할정복 비적용 사례
4.1 임계값(Threshold)
•
문제 크기가 충분히 작아지면, 단순 알고리즘이 재귀 호출보다 효율적
•
최적 임계값 t 계산:
◦
t가 짝수: t = 128
◦
t가 홀수: t = 128.008
4.2 분할정복 비적용 상황
•
분할된 부분의 크기가 거의 n에 가까운 경우 → 지수 시간복잡도
•
예: 피보나치 수열, 부분집합 탐색, 문제를 거의 n개로 쪼개는 경우 등
5. 분할정복 점화식, 트리, 마스터 정리(Master Theorem)
5.1 분할정복 점화식 예시
•
T(n)=T(n/2)+nT(n) = T(n/2) + nT(n)=T(n/2)+n ⇒ O(n)O(n)O(n)
•
T(n)=2T(n/2)+nT(n) = 2T(n/2) + nT(n)=2T(n/2)+n ⇒ O(nlogn)O(n \log n)O(nlogn)
•
T(n)=4T(n/2)+nT(n) = 4T(n/2) + nT(n)=4T(n/2)+n ⇒ O(n2)O(n^2)O(n2)
•
T(n)=3T(n/2)+nT(n) = 3T(n/2) + nT(n)=3T(n/2)+n ⇒ O(nlog23≈n1.58)O(n^{\log_2 3} \approx n^{1.58})O(nlog23≈n1.58)
5.2 마스터 정리(Master Theorem)
•
점화식:T(n)=aT(n/b)+O(nd)
T(n)=aT(n/b)+O(nd)T(n) = aT(n/b) + O(n^d)
•
해:
◦
a<bd ⟹ T(n)=O(nd)a < b^d \implies T(n) = O(n^d)a<bd⟹T(n)=O(nd) (Top에서 연산량 지배)
◦
a=bd ⟹ T(n)=O(ndlogn)a = b^d \implies T(n) = O(n^d \log n)a=bd⟹T(n)=O(ndlogn) (모든 레벨 연산량 동일)
◦
a>bd ⟹ T(n)=O(nlogba)a > b^d \implies T(n) = O(n^{\log_b a})a>bd⟹T(n)=O(nlogba) (Bottom에서 연산량 지배)
5.3 트리 해석 예시
•
Tall and skinny tree: T(n)=T(n/2)+nT(n) = T(n/2) + nT(n)=T(n/2)+n, Top work dominates
•
Bushy tree: T(n)=4T(n/2)+nT(n) = 4T(n/2) + nT(n)=4T(n/2)+n, Bottom work dominates
•
Just right: T(n)=2T(n/2)+nT(n) = 2T(n/2) + nT(n)=2T(n/2)+n, Work per level 동일, 전체 O(nlogn)O(n \log n)O(nlogn)
