[Algorithm] Divide and Conquer, 분할 정복

Divide and Conquer

Divide and Conquer 는 분할정복 알고리즘이라고도 하며, 문제를 2개 또는 그 이상의 작은 부분 문제로 나눠서 문제를 해결하는 알고리즘을 말합니다. 경우에 따라서는 푼 다음에 다시 부분 문제들을 합쳐서 정답을 구할 때도 있으며 퀵 정렬, 병합정렬, 큰수곱셈, FFT 등 여러 분야에서 분할정복 알고리즘을 이용하여 문제를 해결하고 있습니다.

 

Divide and Conquer VS danamic programming

분할정복 알고리즘과 다이나믹 프로그래밍은 문제를 해결하는 핵심적인 전략이 동일합니다. 바로 문제를 작은 부분 문제로 나눠서 해결한다는 점입니다.

하지만 둘은 결정적인 차이가 존재하는데 바로 memorization 입니다.

다이나믹 프로그래밍은 작은 부분 문제 나눌 경우, 부분 문제들이 겹치는 현상이 발생하여 이를 memorization, 즉 기록해두었다가 다음 번에 다시 이용하는 반면, 분할정복 알고리즘은 부분 문제가 겹치지 않기 때문에 memorization 을 해줄 필요가 없습니다.

 

merge sort

위에서도 언급했지만 분할정복 알고리즘을 대표하는 것 중 하나가 바로 merge sort, 병합 정렬 입니다.

수학자인 존 폰 노이만이 1945년에 개발한 알고리즘으로 분할하는데 O(logN), 다시 합치는데 O(N) 의 시간복잡도로 총 O(NlogN) 의 시간복잡도를 가집니다.

partition 이라는 함수는 주어진 배열에 대해 이분하는 함수입니다. 크기가 1이 될 때까지 배열을 계속 분할하기 때문에 재귀적으로 partition 함수를 호출합니다. 모든 문제가 이렇지는 않지만, 최소 단위의 크기가 나올 때까지 계속 해서 분할해야 하기 때문에 주로 재귀적인 형태로 많이 구성합니다.

#include<iostream>

using namespace std;

int N,arr[1000001];
int arr2[1000001];

void merge(int left, int right)
{
    int mid = (left + right) / 2;
    
    int i = left;
    int j = mid + 1;
    int k = left;
    // 작은 값을 먼저 채워서 정렬
    while (i <= mid && j <= right)
    {
        if (arr[i] <= arr[j])
            arr2[k++] = arr[i++];
        else
            arr2[k++] = arr[j++];
    }
    // 한 쪽 배열의 값을 모두 사용했을 때, 남은 배열의 남은 값들을 뒤에 붙이기
    while(i<=mid) arr2[k++] = arr[i++];
    while(j<=right) arr2[k++] = arr[j++];

    for (int i=left;i<=right;i++) arr[i] = arr2[i];
}

void partition(int left,int right)
{
    if (left == right) return;
    
    int mid = (left + right) / 2;
    // 두 개의 부분 문제로 분할
    partition(left, mid);
    partition(mid + 1, right);
  	// 나눈 부분 문제를 통합
    merge(left, right);
    
}

int main()
{
    cin >> N;

    for (int i=0;i<N;i++) cin >> arr[i];
    
    partition(0, N - 1);
    
    for (int i=0;i<N;i++) cout << arr[i] << " ";
}