알고리즘 - 분할정복(Divide & Conquer)

 

1. 분할정복 이란?

 

알고리즘 디자인 패러다임 중 하나이다. 

정의 : 문제를 즉각 해결할 수 있을 때까지 재귀적으로 둘 이상의 하위 문제(Sub-problem)들로 나누고(Divide) 문제를 해결한 다음(Conquer) 그 결과를 이용해 다시 전체 문제를 해결하며 합치는 방법

 

분할정복 방식으로 해결되는 문제들은 예를 들면 다음과 같다.

① 정렬문제(퀵 정렬 - 참조, 병합 정렬 - 참조)
② 큰 숫자 곱하기(Karatsuba 알고리즘) : n자리 수 2개를 곱하여 결과를 나타내는 알고리즘
③ 이진 탐색(Binary Search - 참조)
④ Closest Pair of Points 문제 : 모든 point의 쌍의 거리 중 최소의 거리를 찾는 문제
⑤ Strassens's 알고리즘 : 두 행렬을 곱하는 효과적인 알고리즘
⑥ Cooley-Tukey Fast Fourier Transform(FFT) 알고리즘 : 가장 일반적인 FFT 알고리즘

 

분할정복 관련 내용을 찾아보며 적었는데, 전혀 모르는 내용들도 있다. 그러한 내용은 별도의 검색을 통해 알아보자.

 

분할정복의 핵심 진행방식은 다음과 같다.

① 분할 : 동일한 타입의 하위 문제로 큰 문제를 분할한다.
② 정복 : 재귀적으로 하위 문제들을 해결한다.
③ 병합 : 적절히 해결된 결과를 사용해 큰 문제를 해결한다.

 

 

2. 분할정복의 예 - 병합 정렬

 

상단에 링크가 이미 걸려 있지만, 여기서 한 번 다시 보자.

우선 애니메이션을 보자.

병합 정렬. 출처 : https://velog.io/@emily0_0/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Merge-Sort

너무나 쉽게 이해가 가능한 병합 정렬의 예시이다.

순서에 따라 살펴보면 다음과 같다.

① 분할 : 전체 데이터를 반으로 지속적으로 분할한다. 직접 문제가 해결되는 수준까지(1개 남을 때까지)
② 정복 : 데이터가 1개가 남으면 그 자체로 이미 정렬된 상태이다. 분할된 2개의 데이터를 정렬한다.(하위 문제 해결)
③ 병합 : 정렬된 하위 문제를 병합하여 전체 내역을 정렬한다.

 

분할정복을 위한 병합 정렬의 코드는 다음과 같다.

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];
        }
    }
}

 

 

3. 분할정복과 동적 프로그래밍(Dynamic Programming의 차이점)

 

분할 정복과 동적 프로그래밍은 주어진 문제를 작게 쪼개서 하위 문제로 해결하고 연계적으로 큰 문제를 해결한다는 점은 같다.

차이점은, 분할 정복은 분할된 하위 문제가 동일하게 중복이 일어나지 않는 경우에 쓰며, 동일한 중복이 일어나면 동적 프로그래밍을 쓴다는 것이다.

 

예를 들어, 위의 병합 정렬을 보자.

병합 정렬을 수행 시에 작은 하위 문제로 쪼개지지만 중복하여 하위 문제가 발생하지 않는다. 무슨 말이냐면, 분할된 부분 부분은 모두 독립적이고, 동일한 부분을 중복하지 않는다는 것이다!

 

중복되는 경우는 어떤 것인가? 피보나치 수열을 생각해보자. 피보나치 수열은 $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이 어떤 수이든, 그 하위 수를 구하는 부분은 중복해서 나타난다!

 

그래서 병합 정렬은 분할 정복으로, 피보나치 수열은 동적 프로그래밍으로 해결이 가능한 것이다.

 

또한, 분할정복은 Top-Down만 가능하지만 동적 프로그래밍은 Bottom-up도 가능하다.

 

 

긴 글 읽어주셔서 감사하며, 오류가 있으면 말씀주시면 수정하겠습니다.

이후 관련 문제들을 풀며 포스팅 진행할 것이고 해당 글들은 다음과 같은 Tag로 엮입니다.
(분할정복)