PDF 정리본 (출력 가능)
분할 정복 알고리즘
- 주어진 문제의 입력을 분할하여 문제를 해결(정복)하는 방식의 알고리즘
: 분할한 입력에 대해 동일한 알고리즘을 적용하여 해를 계산
: 이들의 해를 취합하여 원래 문제의 해를 얻음
- 부분 문제와 부분 해
: 분할된 입력에 대한 문제를 부분 문제라고 함
: 부분 문제의 해를 부분 해라고 함
: 부분 문제는 더 이상 분할할 수 없을 때까지 분할함.
- 대부분의 분할 정복 알고리즘은 문제의 입력을 단순히 분할만 해서는 해를 구할 수 없고, 분할된 부분 문제들을 정복해야 함.
Q. 입력 크기가 n일 때 총 몇 번 분할하여야 더 이상 분할할 수 없는 크기인 1이 될까?
A. 답을 계산하기 위해 분할한 총 횟수를 k라고 하면 n/2k = 1일 때 더 이상 분할할 수 없으므로, k = log2n임을 확인할 수 있다.
- 분할 정복 알고리즘의 분류
: 문제가 a개로 분할되고, 부분 문제의 크기가 1/b로 감소하는 알고리즘
a | b | Alg |
2 | 2 | 합병정렬, 최근접 점의 쌍 찾기, 공제선 문제 |
3 | 2 | 큰 정수의 곱셈 |
4 | 2 | 큰 정수의 곱셈 |
7 | 2 | 스트라센의 행렬 곱셈 알고리즘 |
: 문제가 2개로 분할되고, 부분 문제의 크기가 일정하지 않은 크기로 감소하는 알고리즘 ⇒ 퀵 정렬
: 문제가 2개로 분할되나, 그 중에 1개의 부분 문제는 고려할 필요가 없으며, 부분 문제의 크기가 1/2로 감소하는 알고리즘 ⇒ 이진 탐색
: 문제가 2개로 분할되나, 그 중에 1개의 부분 문제는 고려할 필요가 없으며, 부분 문제의 크기가 일정하지 않은 크기 로 감소하는 알고리즘 ⇒ 선택 문제 알고리즘
: 부분 문제의 크기가 1, 2개씩 감소하는 알고리즘 ⇒ 삽입 정렬, 피보나치 수의 계산
3.1 합병 정렬(Merge Sort)
- 합병 정렬
: n개의 숫자들을 n/2개씩 2개의 부분 문제로 분할
: 각각의 부분 문제를 순환으로 합병 정렬
: 2개의 정렬된 부분을 합병하여 정렬(정복)
⇒ 합병 과정이 문제를 정복하는 것임.
Alg MergeSort(A, p, q) input array A of size n, integer p, integer q output sorted array A if(p < q) { k = ⌊(p + q) / 2⌋ MergeSort(A, p, k) MergeSort(A, k+1, q) Merge array A from p to q } |
- 시간 복잡도
: 분할하는 부분
⇒ 배열의 중간 인덱스 계산과 2번의 순환 호출. O(1)
: 합병하는 부분
⇒ 각 계층에서 모든 숫자가 합병에 참여하고 있으므로, 합병의 수행 시간은 합병되는 입력 크기에 비례한다.
각 층에서 O(n). 층수는 log2n.
: 합병 정렬의 시간 복잡도
⇒ (층수) × O(n) = log2n × O(n) = O(nlogn)
- 합병 정렬의 단점
: 대부분의 정렬 알고리즘들은 입력을 위한 메모리 공간과 O(1) 크기의 메모리 공간만을 사용하면서 정렬을 수행함.
: 합병 정렬은 입력을 위한 메모리 공간외에 추가로 입력과 같은 크기의 공간(임시 배열)이 별도로 필요함.
⇒ 2개의 정렬된 부분을 하나로 합병하기 위해, 합병된 결과를 저장할 곳이 필요하기 때문임.
: 합병 정렬의 공간 복잡도
⇒ O(n)
- Applications
: 합병 정렬은 외부 정렬의 기본이 되는 정렬 알고리즘
: 연결 리스트에 있는 데이터를 정렬할 때 퀵 정렬이나 힙 정렬보다 훨씬 효율적임.
: 멀티코어 CPU와 다수의 프로세서로 구성된 그래픽 처리 장치의 등장으로 정렬 알고리즘을 병렬화하는데에 합병 정렬 알 고리즘이 활용됨.
3.2 퀵 정렬(Quick Sort)
- 퀵 정렬 알고리즘은 문제를 2개의 부분 문제로 분할함.
: 사실 알고리즘이 수행되는 과정을 살펴보면 정복 후 분할하는 알고리즘
- 퀵 정렬의 아이디어
: 피봇 원소를 기준으로 피봇보다 작은 숫자들 은 왼편으로, 피봇보다 큰 숫자들은 오른편으 로 위치시키고 피봇을 그 사이에 놓는다.
: 분할된 부분 문제들에 대해서도 위와 동일한 과정을 순환으로 수행하여 정렬한다.
Alg QuickSort(A, left, right) input array A of size n, integer left, integer right output sorted array A 1. if(left < right) { 2. 피봇을 A[left]~A[right]에서 선택 피봇을 A[left]와 자리 변경 피봇과 배열의 원소를 비교 피봇보다 작은 숫자는 A[left]~A[p-1] 피봇보다 큰 숫자는 A[p]~A[right] A[p] = pivot 3. QuickSort(A, left, p-1) 4. QuickSort(A, p+1, right) } |
int partition(int list[], int left, int right) { int pivot, temp, low, high; pivot = list[left]; low = left; high = right + 1; do { do low++; while(list[low] < pivot); do high--; while(list[high] > pivot); if(low < high) SWAP(list[low], list[high], temp); } while(low < high); SWAP(list[left], list[high], temp); return high; } void quickSort(int list[], int left, int right) { if(left < right) { int q = partition(list, left, right); quickSort(list, left, q - 1); quickSort(list, q + 1, right); } } |
- 최악 경우 시간 복잡도
: 항상 최소 숫자가 선택되는 경우
⇒ (n-1)+(n-2)+…+2+1 = n(n-1)/2
즉, O(n2)
단, pivot이 랜덤하게 선택될 때, 이런 결과가 나올 확률은 낮다는 것이 과학적으로 증명되었다.
- 최선의 경우 시간 복잡도
: 항상 1/2로 분할되는 경우
⇒ 총 비교 횟수 = O(n) × (층수)
= O(n) × logn
즉, O(nlogn)
- 평균 경우 시간 복잡도
: 피봇을 항상 랜덤하게 선택한다고 가정
⇒ O(nlogn)
- 피봇 선정 방법
: 세 숫자의 중앙값으로 피봇을 선정하는 방법
⇒ Median-of-Three
: 삼등분한 후 각 부분에서 가장 왼쪽 숫자, 중 간 숫자, 가장 오른쪽 숫자 중에서 중앙값을 찾은 후, 세 중앙값들 중에서 중앙값을 피봇으로 선정하는 방법
⇒ Median-of-Medians
- 성능 향상 방법
: 입력의 크기가 매우 클 때, 퀵 정렬의 성능을 더 향상시키기 위해서 삽입 정렬을 동시에 사용
: 입력의 크기가 작을 때에는 순환 호출로 수행되는 퀵 정렬이 삽입 정렬보다 느림.
⇒ 부분 문제의 크기가 작아지면 더 이상의 분할(순환 호출)을 중단하고 삽입 정렬을 사용
- Applications
: 퀵 정렬은 커다란 크기의 입력에 대해서 가장 좋은 성능을 보이는 정렬 알고리즘
: 퀵 정렬은 실질적으로 어느 정렬 알고리즘보다 좋은 성능을 보임.
'컴퓨터 알고리즘' 카테고리의 다른 글
[컴퓨터알고리즘] Ch 3. 분할 정복 알고리즘(2) (0) | 2022.04.19 |
---|---|
[컴퓨터알고리즘] Ch 2. 알고리즘을 배우기 위한 준비 (0) | 2022.04.14 |
[컴퓨터알고리즘] Ch 1. 알고리즘의 첫걸음 (0) | 2022.04.14 |