Divide and Conquer

Divide and Conquer

크기 N짜리 문제에 대해 top-down 방식으로 하여 "재귀적"으로 문제를 푸는 알고리즘

• 크기 N짜리 문제를 N보다 크기가 작은 subproblems으로 나눈다 (Divide)
• subproblems를 기존의 방식으로 풀어낸다(recursive). (Conquer)
• 이때 subproblems가 크기 N에 대해 "모두" 고려해야한다.

Merge Sort

N개의 크기를 가지는 array를 nondecreasing하게 정렬하기

크기 N인 array에 대해 N/2 인 subarray로 나누어 문제를 해결

$$T(n)=2T(\cfrac{n}{2})+cn$$

• $T(n)$ : 입력 크기가 $n$인 문제를 해결하는 데에 드는 비용

Base Step

가장 크기가 작은 입력데이터에 대한 결과를 고려해야 한다.

Merge Sort에서는 입력데이터가 하나인 경우이다. 입력데이터의 크기가 하나일 경우 Divide를 종료하고 Merge를 시작한다.

$$T(1)=1$$

Merge

입력으로 두 subarray가 들어오면 두 subarray를 각각 돌면서 nondecreasing으로 정렬되게 두 배열을 합친다.

이때 입력으로 들어온 subarray는 이미 nondecreasing 상태이다.

Time Complexity

Divide	Conquer	Combine
$O(1)$	$2T(n/2)$	$O(n)$

⇒ $T(n) = O(nlogn)$

Example Code

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef int item_type;

int N;
item_type *buffer;

void print_array(item_type* A)
{
    for(int i=0; i<N; i++)
    {
        printf("%d ",A[i]);
    }
    printf("\n");
}

void merge(item_type *A, int left, int mid, int right)
{
    int i, i_left, i_right;

    memcpy(buffer+left, A+left, sizeof(item_type)*(right-left+1));

    i_left=left;
    i_right=mid+1;
    i=left;

    while((i_left<=mid)&&(i_right<=right)){
        if(buffer[i_left]<=buffer[i_right])
            A[i++]=buffer[i_left++];
        else A[i++]=buffer[i_right++];
    }

    while(i_left <= mid)
         A[i++]=buffer[i_left++];

    while(i_right <= right)
         A[i++]=buffer[i_right++];
}

void merge_sort(item_type *A, int left, int right)
{
    int mid;

    if (left < right)
    {
        mid = (left+right)/2;

        merge_sort(A, left, mid);
        merge_sort(A, mid+1, right);

        merge(A, left, mid, right);
    }
}

int main(void)
{
    item_type *A;
    int i;

    printf("Enter the size of array: ");
    scanf("%d", &N);

    buffer = (item_type*)malloc(sizeof(item_type)*N);
    A = (item_type*)malloc(sizeof(item_type)*N);

    printf("Enter the array A: ");
    for(i=0; i<N; i++){
        scanf("%d", &A[i]);
    }

    merge_sort(A, 0, N-1);

    print_array(A);

    free(A);
    free(buffer);

    return 0;
}

서강대학교 임인성 교수님 알고리즘 수업을 기반으로 작성한 문서입니다