divide and conquer - 분할정복 알고리즘

1. 분할 정복 - 기본편

• 그대로 해결할 수 없는 문제를 "작은" 문제로 분할하여 문제를 해결하는 방법.
• 대표적으로 "병합정렬" 
• 분할 정복에는 3가지 용어로 정리 할 수 있다.

Divide	문제를 더 작은 단위로 가능할 때 까지 나눔
Conquer	각 하위 문제를 재귀로 해결, 탈출조건을 설정해 나눌 수 없는 단계에서는 문제를 해결
Combine (merge)	conquer가 된 문제들을 합쳐서 점차적으로 원래의 문제의 답을 찾아 나감

• 쉬운 예시로 1 ~ 8 까지의 합을 생각해보자

1 2 3 4 5 6 7 8
# 1~8의 합

divide (1회)
# 1~4의 합, 5~8의 합

1 2 3 4 || 5 6 7 8 

divide (2회)
# 1~2의 합, 3~4의 합, 5~6의 합, 7~8의 합

1 2 || 3 4 || 5 6 || 7 8

divide (3회)
# 1의 합, 2의 합, 3의 합, 4의 합, 5의 합, 6의 합, 7의 합, 8의 합

1 || 2 || 3 || 4 || 5 || 6 || 7 || 8

• 1 ~ 8 까지의 합을 큰 문제로 생각한다면, 이를 재귀로 쪼개서 분할 할 수 있다.
• 가장 밑 단계 까지 가면 각각의 원소의 합을 구할 수 있다. (종료조건을 원소 1개로 설정했다고 가정한다.) 이를 base case라고 한다.
• base case : 더 이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제
• 그런 다음 병합 과정을 가진다. (merge)

#역순으로 merge

#원소의 갯수가 1개에서 2개
1의 결과 + 2의 결과 = 3 || 3의 결과, 4의 결과 = 7 || 5의 결과, 6의 결과 = 11 || 7의 결과, 8의 결과 = 15

#원소의 갯수가 2개에서 4개
3 + 7 || 11 + 15

#원소의 갯수가 4개에서 8개 == 문제가 풀림
10 + 26

#1~8까지의 합은 36임을 알 수 있다.

2.분할정복 - 활용편 (병합 정렬)

• 대표적인 예시 병합 정렬 (6,8,1,3,2,5,4,7)

•  divide (1회) : 원소의 갯수 8개 -> 4개 (6,8,1,3 || 2,5,4,7)

•  divide (2회) : 원소의 갯수 4개 -> 2개 (6,8 || 1,3 || 2,5 || 4,7)

•  divide (3회) : 원소의 갯수 2개 -> 1개 (6,8 || 1,3 || 2,5 || 4,7)

•  종료조건에 도달했으니 이제 완료된 결과를 각각 합쳐야 한다. (Combine, merge)
•  merge (1회) : 원소의 갯수 1개 -> 2개 (6,8 || 1, 3 || 2, 5 || 4 ,7 )
• (주인장이 예시를 좀 잘 못 만들긴 했는데, 아래 기준처럼 정렬을 합니다.)

• merge (2회) : 원소의 갯수 2개 -> 4개 (1, 3, 6, 8 || 2, 4, 5, 7)

• merge (3회) : 원소의 갯수 4개 -> 8개 (1, 3, 6, 8 || 2, 4, 5, 7)

3. 병합정렬 소스코드 (cpp)

#include <iostream>

#define fast ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
using namespace std;
int N;
// # A[p..q]와 A[q+1..r]을 병합하여 A[p..r]을 오름차순 정렬된 상태로 만든다.
// # A[p..q]와 A[q+1..r]은 이미 오름차순으로 정렬되어 있다.
void merge(int arr[], int p, int q, int r)
{
    int i, j, t;
    int *tmp = new int[N];
    i = p;
    j = q + 1;
    t = 0;
    while (i <= q && j <= r)
    {
        if (arr[i] <= arr[j])
            tmp[t++] = arr[i++];
        else
            tmp[t++] = arr[j++];
    }
    while (i <= q)  // 왼쪽 배열 부분이 남은 경우
        tmp[t++] = arr[i++];
    while (j <= r)  // 오른쪽 배열 부분이 남은 경우
        tmp[t++] = arr[j++];
    i = p;
    t = 0;
    while (i <= r) // 결과를 A[p..r]에 저장
        arr[i++] = tmp[t++];
    delete[] tmp;
}

void merge_sort(int arr[], int p, int r)
{
    int q;
    if (p < r)
    {
        q = (p + r) / 2;       // q는 p, r의 중간 지점
        merge_sort(arr, p, q);      // 전반부 정렬
        merge_sort(arr, q + 1, r);  // 후반부 정렬
        merge(arr, p, q, r);        // 병합
    }
}

int main()
{
    fast;
    cin >> N;
    int *arr = new int[N];

    for (int i = 0; i < N; i++) //초기 입력 받기 예제로 치면 68132547
        cin >> arr[i];
    merge_sort(arr, 0, N-1);

    delete[] arr;
}