분할 정복(Divide and Conquer)은 여러 알고리즘의 기본이 되는 해결방법으로, 기본적으로 엄청나게 크고 방대한 문제를 조금씩 조금씩 나눠가면서 용이하게 풀수 있는 문제 단위로 나눈 다음 그것들을 다시 함쳐서 해결하자는 개념이다.
문제를 즉각 해결할 수 있을 때까지 재귀적으로 둘 이상의 하위 문제(sub-problem)들로 나누고(Divide)문제를 해결한 다음(conquer)그 결과를 이용해 다시 전체 문제를 해결하며 합치는 방법
분할정복 방식을 사용하여 해결할 수 있는 문제들
- 정렬문제(퀵 정렬, 병합 정렬)
- 큰 숫자 곱하기(Karatsuba):n자리 수 2개를 곱하여 결과를 나타내는 알고리즘
- 이진 탐색(Binary Search)
- Closest Pair of Points문제:모든 point 쌍의 거리 중 최소의 거리를 찾는 문제
- Strassens's알고리즘:두 행렬을 곱하는 효과적인 알고리즘
- Cooley-Tukey Fast Fourier Transoform(FFT)알고리즘
분할정복의 진행방식
step.1 분할 : 동일한 타입의 하위 문제로 큰 문제를 분할한다.
step.2 정복 : 재귀적으로 하위 문제들을 해결한다.
step.3 병합 : 적절히 해결된 결과를 사용해 큰 문제를 해결한다.
병렬정렬로 예를 들면 다음과 같다.
step.1 분할 : 전체 데이터를 반으로 지속적으로 분할한다. (직접 문제가 해결되는 수준까지)
step.2 정복 : 데이터가 1개가 남으면 그자체로 이미 정렬된 상태이다.
분할된 2개의 데이터를 정렬한다.(하위 문제 해결)
step.3 병합 : 정렬된 하위 문제를 병합하여 전체 내역을 정렬한다.
public class MergeSort{
public static void main(String[] args){
int[] arr = new int[100];
for(int i=0; i < arr.length; i++){
arr[i] = (int)(Math.random() * 100);
}
mergeSort(arr, 0, arr.length-1);
for(int i=0; i < arr.length; i++){
System.out.print(arr[i] + ", ");
}
}
public static void mergeSort(int[] arr, int start, int end){
if(start == end) return;
int mid = (start+end)/2;
mergeSort(arr, start, mid);
mergeSort(arr, mid+1, end);
int[] temp = new int[end-start+1];
int idx = 0;
int left = start;
int right = mid+1;
while(left <= mid && right <= end){
temp[idx++] = arr[left] <= arr[right] ? arr[left++] : arr[right++];
}
while(left <= mid){
temp[idx++] = arr[left++];
}
while(right <= end){
temp[idx++] = arr[right++];
}
for(int i=start; i <= end; i++){
arr[i] = temp[i-start];
}
}
}cf)동적프래그래밍과 분할정복의 차이점
분할 정복과 동적 프로그래밍은 주어진 문제를 작게 쪼개서 하위 문제로 해결하고 연계적으로 큰 문제를 해결한다는 점은 같다.
차이점은, 분할 정복은 분할된 하위 문제가 동일하게 중복이 일어나지 않는 경우에 쓰며, 동일한 중복이 일어나면 동적 프로그래밍을 쓴다는 점이다.
예를 들어 위의 병합 정렬을 보자
병합 정렬을 수행 시에 작은 하위 문제로 쪼개지지만 중복하여 하위 문제가 발생하지 않는다. 왜냐하면 분할된 부분 부분은 모두 독립적이고, 동일한 부분을 중복하지 않는다는 것이다.
중복이되는 경우는 어떤 경우인가?
피보나치 수열의 경우 f(n)=f(n-1)+f(n-2)라는 수식을 갖는다.
따라서 n이 어떤 수가 되던,n-1번째 수와 n-2번째 수를 더해야 한다.
예를 들어서 n=5인경우 n-1은 4이고 n-2는 3인데 3을 구하기 위해서는 n-2가 1인 경우까지 하위 문제로 내려가야한다.
이러한 경우 n이 어떤 수이든, 그 하위 수를 구하는 부분은 중복해서 나타난다.
그래서 병합 정렬은 분할 정복으로, 피보나치 수열은 동적 프로그래밍으로 해결이 가능하다.
cf)아래 블로그에 들어가면 행렬과 분할정복 기반의 피보나치 수 알고리즘을 보여주고 있다.
https://nukestorm.tistory.com/149
