[알고리즘] 3. Divide and Conquer
1. Divide and Conquer 분할 정복 개념
: Divide and Conquer는 문제를 해결하기 위해 다음과 같은 3단계를 거친다.
- Divide(분할): 문제 인스턴스를 하나 또는 여러 개의 더 작은 인스턴스로 나눈다.
- Conquer(정복): 작은 인스터스를 재귀적으로 해결한다. → 충분히 작아지면 더 이상 분할하지 않고 직접 해결
- Combine(결합): 작은 인스턴스의 해를 합쳐서 원래 문제의 해를 만든다.
이 방식은 Top-down 접근이며, 재귀적으로 구조화된다.
2. 이진탐색
: 대표적인 Divide & Conquer
문제정의
- 입력: 정렬된 배열 S (크기 n), 찾을 값 x
- 출력: x의 위치 (없으면 0)
수행 방법
- 배열의 중간값 S[mid]를 기준으로
- x가 작으면 왼쪽 반, 크면 오른쪽 반을 다시 탐색
- 재귀적으로 반복 -> 배열 크기가 1 이하가 될 때까지
코드 (재귀함수)
location(low, 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);
}
꼬리 재귀 구조로, 재귀 이후에 다른 작업이 없으므로 반복문으로 쉽게 전환 가능 → 반복문이 보통 더 빠름 (스택 사용 안하니까)
이진 탐색의 시간 복잡도 분석
- x == S[mid] 와 같은 비교 연산
- 입력 크기: n(배열의 길이)
- 수학적 귀납법에 의한 증명
- basis ex. n=1 → 비교 1회 → W(1)=1= log₂1 + 1
- 귀납 가정: W(n) = log₂1 + 1
- 귀납 단계: W(2n) = log₂1 + 1 = log₂1 + 1 + 1 = log₂(2n) + 1 → W(n) = ⌊log₂n⌋ + 1
- 즉, 이진 탐색의 worst 시간복잡도는 O( log n )
3. Merge Sort
: 정렬 알고리즘 (분할정복 사용)
절차
- Divide: 배열을 두개로 분할 (각각 n/2)
- Conquer: 각각을 재귀적으로 정렬
- Combine: 두 정렬된 배열을 병합(merge)
void mergesort(n, S[]) {
if (n > 1) {
split S into U and V;
mergesort(U); mergesort(V);
merge(U, V, S);
}
}
병합 과정
- 두 정렬된 배열 U, V를 비교하며 하나로 병합
- 각 배열에서 더 작은 값을 결과 배열에 차례로 복사
ex.
- U: 10, 12, 20, 27
- V: 13, 15, 22, 25
- 병합 결과: 10, 12, 13, 15, 20, 22, 25, 27
Merge Sort의 시간 복잡도 분석
- merge 단계에서 최대 (n-1)번의 비교
- 재귀 호출에 따라 총 비교 수는 다음과 같다 : W(n) = W(n/2) + W(n/2) + (n - 1)
- 재귀식: T(n) = 2T(n/2) + O(n) → Master Theorem에 의해 O(n log n)
4. Quick Sort (분할 교환 정렬)
: 피벗(pivot)을 기준으로 작은 값과 큰 값을 분할
절차
- partition() 함수로 피벗 기준으로 좌우 분할 → 각 부분을 재귀적으로 퀵 정렬
void quicksort(low, high) {
if (high > low) {
partition(low, high, pivot);
quicksort(low, pivot-1);
quicksort(pivot+1, high);
}
}
Partition 알고리즘
: pivot 기준으로 작으면 왼쪽, 크면 오른쪽으로 나누기
- 피벗은 보통 S[low]로 설정
- i는 현재 검사 위치, j는 피벗보다 작은 값의 경계, i>j 이면 교환
Worst 시간복잡도
:O(n²) → 이미 정렬된 배열 등에서 발생
5. Master Theorem
: 재귀식 시간 복잡도 해석 도구
- T(n) = aT(n/b) + f(n)
- T(n)이 단조 증가하지 않으면 적용 불가
- f(n)이 다항식이 아닌 경우도 적용 불가
EX1: T(n) = 2T(n/4) + √n + 42
- a = 2, b = 4, d = 1/2
→ 2 = 4^{1/2} → a = bᵈ → case 2
→ T(n) = Θ(n^{1/2} log n)
EX2: T(n) = 3T(n/2) + (3/4)n + 1
- a = 3, b = 2, d = 1
→ 3 > 2¹ → case 3
→ T(n) = Θ(n^log₂3)
6. Strassen's Matrix Multiplication
기존 방법
- 곱셈: 8회
- 덧셈/뺄셈: 4회
Strassen 방법
- 곱셈: 7회
- 덧셈/뺄셈: 18회 → 큰 입력에 유리
시간복잡도
- T(n) = 7T(n/2) + O(n²) : Master Theorem 적용 → Θ(n^log₂7) ≈ Θ(n^2.81)
7. Divide & Conquer의 한계
사용을 피해야 할 경우
- 문제 크기 n을 거의 유지한 채로 여러 개로 분할 → 지수 시간
- n개의 크기 n/c인 인스턴스로 나누는 경우 → Θ(n log n)보다 악화
8. Closest Pair 문제
1D에서의 최적해
- 정렬 후 양쪽으로 나누어 재귀적으로 해결
- 분할/정복 과정에서도 가장 가까운 점은 왼쪽 끝/ 오른쪽 시작에 있다.
- 시간 복잡도: O(n log n)
2D에서의 복잡성
- δ-strip 내에서의 점들을 분석
- 직사각형 내에 있는 점 쌍 비교 → 최대 6개
- 최종 시간복잡도: O(n log n)유지 가능