Divide and Conquer(분할정복)과 병합정렬

출처 : https://www.codeground.org/common/popCodegroundNote#

분할정복(Divide and Conquer)은 말 그대로 문제를 분할한 다음, 분할한 문제들(Sub-problems)을 해결하고,

그 결과를 합쳐서 원래의 문제를 해결하는 것입니다. 분할 후 문제를 해결하는 알고리즘은 임의로 선택할 수 있습니다.

분할정복의 대표적 예로는 합병정렬, 퀵정렬, (퀵정렬이 합병정렬보다 빠르다.)고속 푸리에 변환 등이 있습니다.

어려운 문제를 나누어 해결하기 때문에 효율적으로 문제를 해결할 수 있는 여러 알고리즘이 있으며(ex 합병정렬은 (O(NlogN))

병렬적으로 문제를 해결하는 큰 강점이 있습니다.

하지만 스택에 다양한 데이터를 보관하고 있어야 하므로 스택 오버플로우가 발생하거나 과도한 메모리 사용을 하게 되는 단점이 있습니다.

합병정렬을 예로 설명해보겠습니다.

영역을 나눈 후, 나누어진 영역을 투 포인터(Two Pointer) 알고리즘으로 합병하는 방식으로 동작합니다.

투 포인터 알고리즘을 사용하려면 나눠진 영역이 정렬이 되어있어야 하기 때문에

먼저 영역을 작게 나눈 후 합치는 재귀적인 방법이 사용됩니다.

이진탐색과 유사하게 전체 영역을 [L,R],M = (L+R)/2이라고 할 때 [L,M],[M+1,R] 두 개의 영역으로 분할 하겠습니다.

위의 분할 정복의 시간 복잡도는 최대 분할 * 합병 = O(logN) * O(n) = O(NlogN)으로 상당히 빠르므로 효율적인 알고리즘으로 볼 수 있습니다.

n의 메모리를 써야하기 때문에 퀵보다 많은 공간을 차지한다.

이 처럼 문제를 쉽게 해결 가능한 문제가 될 때까지 나눈 후 해결하고 합치는 해법을 분할정복이라고 합니다.

하지만 중복이 있는 피보나치 같은 경우는 중복된 Sub-problem으로 이를 분할할 때마다 처리한다면 매우 비효율적일 것입니다.

이와 같은 문제는 분할정복보다는 동적계획법의 Top-Down 접근법(Memoization)으로 접근하는 것이 효율적일 것입니다.

합병정렬의 코드

입력

첫 번째 줄에 정렬해야 하는 원소의 수 N,
두 번째 줄에 정렬해야 할 원소들이 주어집니다.

Sample Input
7
5 1 8 -3 2 6 -5

출력
합병정렬의 결과를 출력합니다.

Sample Output
-5 -3 1 2 5 6 8

#include <iostream>
using namespace std;
int d[100];
int temp[100];
void MergeSort(int L, int R) {
    if (L >= R)return;
    int M = (L + R) / 2;
    //Divide
    MergeSort(L, M);
    MergeSort(M + 1, R);
    //Conquer
    for (int i = L, l = L, r = M + 1;
        l != M + 1 || r != R + 1;
        i++) {//two pointer를 사용하여 합침
        if ((r != R + 1 && l <= M && d[l] < d[r]) || r == R + 1) {
            temp[i] = d[l++];
        }
        else {
            temp[i] = d[r++];
        }
    }
}
int main() {
    int n;
    scanf_s("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &d[i]);
    MergeSort(0, n - 1);

    for (int i = 0; i < n; i++)
        printf("%d ", d[i]);
}