Basic Idea
- 문제의 인스턴스를 둘 이상의 소규모로 분할
- 작은 인스턴스를 재귀적으로 해결
- 이러한 솔루션을 결합해 원래(대규모) 인스턴스에 대한 솔루션 확보
Maximum-subarray problem
ex)
- Input: An array A[1..n]
- 일부 숫자가 음수라고 가정함
- Output: 인덱스 i 및 j
- 여러 해가 나올 수 있음
- 최대 하위 배결을 찾음
Brute Force Solution
- 모든 구간의 합을 전부 계산하여 비교하는 방식
- 시간복잡도는 𝜃(n^2)
Divide and Conquer Solution
- SubProblem: A[low .. high]의 subarray의 최대값을 찾음
- 원래 호출에서는 low = 1, high = n임
- Divide: 하위 배열을 가능한 같은 크기의 두 하위 배열로 나눔
- 하위 배결의 중간 지점을 찾고 하위 배열 A[low..mid]와 A[mid+1 .. high]를 고려함
- Conquer: 최대값을 갖는 하위 배열 A[low..mid]와 A[mid+1 .. high]를 찾아 정복
- Combine: 교차하는 최대 하위 배열을 찾아 결합함
- 중간 지점, 종항점을 가로지르는 하위 배결과 정복 단계에서 발견된 두 가지 해결책 이 세 가지 중 가장 좋은 솔루션을 사용함
예를 들어 {-3, 0, -1, 3, 5, -2, -4} 의 부분합의 최대값은 3+5로 8이지만 절반으로 나눠 각각 계산하면 이를 구할 수 없습니다.
따라서 작은 문제로 나누기 전, 걸치는 상황에 대해 계산을 우선적으로 해줍니다.
- 시간복잡도는 O(nlogn)
분석
- 가정의 단순화: 원래 문제 크기는 2의 거듭제곱이므로 모든 하위 운제 크기는 정수임
- Base case: low, high가 동일하므로 n = 1일 때 발생함
- 이 절차는 단지 T(n) = 𝜃(1) 반환함
- Recursive case: n이 1보다 클 때 발생함
- Dividing: 𝜃(1)
- Conquering: 각각 n=2 요소의 하위 배열에 있는 두 가지 하위 문제를 해결함
- 각 하위 문제에 대해 T(n/2) 시간 -> 정복에 2T(n/2)시간이 걸림
- Combining: (n) = 𝜃(n) 시간이 소요되며, 결합을 위한 일정한 수의 상수 시간 테스트 포함 -> 𝜃(n) + 𝜃(1) 시간이 소요됨
Mergesort
- A[0..n-1]을 두 개의 동일한 절반의 배열로 나누고 array B, C에서 각 절반의 복사본을 만듦
- 배열 B 및 C를 재귀적으로 정렬
- 정렬된 배열 B와 C를 배열 A로 병합
출처: https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html
분석
- 모든 케이스의 효율성을 동일함
- 𝜃(n log n)
- 최악의 경우 비교 횟수는 comparison-based sorting의 이론적 최솟값에 근접합
- 공간 요구 사항: 𝜃(n) -> not in-place
- 재귀 없이 구현 가능(bottom-up)
- 합병 정렬은 외부 정렬의 기본이 되는 정렬 알고리즘
- 연결 리스트에 있는 데이터를 정렬할 때에도 퀵정렬이나 힙정렬보다 훨씬 효율적!!
참고: Counting Sort
Quicksort
-
Pivot(Prtitioning 요소) 선택
- 보통 첫 번째 혹은 마지막 요소
-
첫 번째 위치의 모든 요소가 피벗보다 작거나 동일하고 나머지 N-s 위치의 모든 요소가 피벗보다 크거나 동일하도록 목록 재정렬
-
피벗을 첫 번째 하위 배열의 마지막 요소와 교환 - 피벗이 이제 최종 위치에 있음
-
두 개의 하위 배열을 재귀적으로 정렬함
- 최적의 경우: 가운데 분할 Θ(n log n)
- 최악의 경우: 정렬된 배열 Θ(n2)
- 평균 경우: 랜덤 배열 Θ(n log n)
-
개선 사항
- 피벗 선택 개선: 3개의 partitioning의 중간값
- 작은 subfile에서 사입 정렬로 전환
- 재귀 제거
-
Quicksort는 대용량 파일의 내부 정렬(n≥ 10000)을 위한 선택 방법으로 간주됨
Binary Tree Alogirithm
- 이진 트리는 분할 및 정복 준비 구조
- ex1) 고전적 순회(preorder, inorder, postorder)
- Algorithm Inorder(T)
- T != ∅이면 순서대로(T 왼쪽); 인쇄(T의 루트); 순서대로(T오른쪽)
- 효율성 : Θ(n)
- Algorithm Inorder(T)
- ex2) 이진 트리의 높이 개선
- h(T) = max{h(TL), h(TR)} + 1 T != ∅ 및 h(θ) = -1이면
- 효율성 : Θ(n)
Multiplication of Large Integer
Matrix Multiplication
Strassen's Matrix Multiplication
Closet Pair Problem
- Divide & Conquer solution
- n개의 점을 1/2로 분할해 각각의 부분 문제에서 최근접 점의 쌍을 찾고, 2개의 부분해 중에서 짧은 거리를 가진 점의 쌍을 일단 찾기
- 2개의 부분해를 취합할 대에는 경계영역에 대해 고려
출처: 
https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=babobigi&logNo=220530321348
