[알고리즘] 분할정복

분할정복 알고리즘이란?

분할정복(Divide and conquer algorithm)은 그대로 해결 할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법이다.

대표적인 예로 퀵정렬 또는 합병정렬과 같은 알고리즘이 있다.

 

알고리즘을 설계하는 요령

- Divide : 문제가 분할이 가능한 경우, 2개 이상의 문제로 나눈다.

- Conquer : 나누어진 문제가 여전히 분할이 가능하면 또 다시 Divide를 수행한다. 그렇지 않으면 문제를 정복한다.

- Combine : : Conquer한 문제들을 통합하여 원래 문제의 답을 얻는다.

※ 문제를 제대로 나누면 conquer 하는 것이 쉽기 때문에 Divide 를 제대로 하는것이 가장 중요하다.

 

 

분할정복 알고리즘 예

function F(x):
  if F(x)의 문제가 간단 then:
    return F(x)을 직접 계산한 값
  else:
    x 를 y1, y2로 분할
    F(y1)과 F(y2)를 호출
    return F(y1), F(y2)로부터 F(x)를 구한 값

출처:나무위키

분할정복의 대표적인 예

 

https://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=2859&sca=3010 

JUNGOL

합병정렬은 John von Neumann 이라는 사람이 개발한 알고리즘이다.

N개의 데이터를 정렬할 때 시간복잡도 O(N * log N)이 보장된다.

정렬의 각 과정은 분할 -> 정복 -> 결합 과정으로 이루어진다.

 

1. Divide :

low,high 구간을 입력 받아 mid  = (low+high)/2 로 중간 위치를 구한다.

2. Conquer :

low~mid 까지 구해 오고 mid+1 ~ high 까지 구해 온다.

3. Combine

low 부터 high 까지 결합한다.

void merge_Sort(int s,int e)
{
    if(s>=e) return;
    int mid = (s+e)/2;

    merge_Sort(s,mid);
    merge_Sort(mid+1,e);

    int i= s;
    int j=mid+1;
    for(int k=s;k<=e;k++)
    {
        if(j>e) temp[k]=num[i++];
        else if(i>mid) temp[k]=num[j++];
        else if(num[i]<=num[j]) temp[k]=num[i++];
        else temp[k] = num[j++];
    }
    for(int k=s;k<=e;k++) num[k]=temp[k];

}