개요[편집 / 원본 편집]
주어진 문제를 작은 사례로 나누고(Divide), 각각의 작은 문제들을 해결하여 정복(Conquer)하는 방법이다. 분할 정복법은 문제의 사례를 2개 이상의 더 작은 사례로 나눈다. 이 작은 사례는 주로 원래 문제에서 따온다. 나눈 작은 사례의 해답을 바로 얻을 수 있으면 해를 구하고 아니면 더 작은 사례로 나눈다.
해를 구할 수 있을 만큼 충분히 더 작은 사례로 나누어 해결하는 방법이다.
분할 정복법은 하향식(top-down) 접근 방법으로 최상위 사례의 해답은 아래로 내려가면서 작은 사례에 대한 해답을 구함으로써 구한다.
설계전략[편집 / 원본 편집]
- 문제 사례를 하나 이상의 작은 사례로 분할(Divide)한다.
- 작은 사례들을 각각 정복(Conquer)한다. 작은 사례가 충분히 작지 않은 이상 재귀를 사용한다.
- 필요하다면, 작은 사례에 대한 해답을 통합(Combine)하여 원래 사례의 해답을 구한다.
분할 정복 사용 예[편집 / 원본 편집]
- 이분검색
- 합병정렬
- 퀵정렬
- 최대값 찾기
- 임계값의 결정
- 쉬트라센 행렬곱셈 알고리즘 등
이분검색[편집 / 원본 편집]
문제 : 10개의 정렬된 배열에서 값을 21가진 인덱스를 찾아라.
low: 0 high: 9 middle: (low + high)/2 => 4.5 => 4
| A(0) | A(1) | A(2) | A(3) | A(4) | A(5) | A(6) | A(7) | A(8) | A(9) |
| 5 | 7 | 10 | 12 | 16 | 20 | 21 | 25 | 28 | 30 |
low: 4 + 1 => 5 high: 9 middle: 7
| A(0) | A(1) | A(2) | A(3) | A(4) | A(5) | A(6) | A(7) | A(8) | A(9) |
| 5 | 7 | 10 | 12 | 16 | 20 | 21 | 25 | 28 | 30 |
low: 5 high: 7 - 1 = 6 middle: 5
| A(0) | A(1) | A(2) | A(3) | A(4) | A(5) | A(6) | A(7) | A(8) | A(9) |
| 5 | 7 | 10 | 12 | 16 | 20 | 21 | 25 | 28 | 30 |
low: 5 + 1 = 6 high: 6
| A(0) | A(1) | A(2) | A(3) | A(4) | A(5) | A(6) | A(7) | A(8) | A(9) |
| 5 | 7 | 10 | 12 | 16 | 20 | 21 | 25 | 28 | 30 |
int[] arr = {5, 7, 10, 12, 16, 20, 21, 25, 28, 30}
public int binarySearch(int target) {
low = 0;
high = arr.length;
while (low <= high) {
middle = (low + high) / 2;
if (target == array[middle]) {
return middle;
} else if (target > array[middle]) {
low = middle + 1;
} else {
high = middle - 1;
}
}
return -1; //not found
}
장단점[편집 / 원본 편집]
장점[편집 / 원본 편집]
- 문제를 나눔으로써 어려운 문제를 해결할 수 있다는 엄청나게 중요한 장점이 있다.
- 이 방식이 그대로 사용되는 효율적인 알고리즘들도 여럿 있으며, 문제를 나누어 해결한다는 특징상 병렬적으로 문제를 해결하는 데 큰 강점이 있다.
단점[편집 / 원본 편집]
- 함수를 재귀적으로 호출한다는 점에서 함수 호출로 인한 오버헤드가 발생한다.
- 스택에 다양한 데이터를 보관하고 있어야 하므로 스택 오버플로우가 발생하거나 과도한 메모리 사용을 하게 된다.