[알고리즘/Algorithm]Divide and conquer, 분할 정복

Divide and Conquer, 분할하고 정복

안녕하세요. Air8입니다. 오늘의 얘기는 분할정복입니다.

이공학도라면 많이 들어봤을 단어인데요. 대체적으로 재귀적인 문제를 해결할 때 사용하는 기법입니다.

 

분할 정복의 접근법은 분할하고 정복한 다음 결합하는 것이라고 할 수 있습니다.

어떤 큰 문제를 여러 개의 작은 문제로 분할하고, 작은 문제는 큰 문제랑 같은 성향을 지녔으나 스케일만 작아진 것입니다. 그 뒤에 작아진 문제를 해결하고 흩어진 작은 문제들을 다 합치는 것으로 볼 수 있습니다.

 

여기서 여러 정렬 알고리즘 중에 Merge sort를 예로 들겠습니다.

 

Merge sort의 흐름

알고리즘 설명

[알고리즘 이름] Merge sort

[속성] Big-O notation = O(n * logn) -> 평균 시간 복잡도 재귀, 분할 정복

[연산] 붉은 화살표 : 분할 녹색 화살표 : 정복(정렬)

코드

void merge_sort(int list[], int left, int right)
{
    if(left >= right)
    	return;
    
    int mid = (left + right) / 2;
    merge_sort(list, left, mid);
    merge_sort(list, mid + 1, right);
    merge(list, left, mid, right);
}

void merge(int list[], int left, int mid, int right)
{
	int sorted[MAX_SIZE];	// 인자를 더 받아 동적할당 가능
    int i, j;
    int k = left;
    
    for(i = left, j = mid + 1; i <= mid && j <= right;)
    {
    	sorted[k++] = (list[i] <= list[j]) ? list[i++] : list[j++];
    }
    
    int p = 0;
    if(i > mid)
    {
    	for(p = j; p <= right; p++, k++)
        	sorted[k] = list[p];
    }
    else
    {
        for(p = i; p <= mid; p++, k++)
        	sorted[k] = list[p];
    }
    for(p = left; p <= right; p++)
    	list[p] = sorted[p];
}

설명(Merge 부분)

이미지 참조 : https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

위와 같이 Merge의 경우에는 양 쪽 파티션에서 index를 생성합니다.

그리고 각 파티션별로 제일 왼쪽이 min값이고 우측으로 갈수록 높아지는 특성을 이용하여 해당하는 인덱스끼리의 값을 비교합니다. 해당하는 인덱스의 값이 낮은 경우에는 index++을 통하여 옆으로 이동합니다. 그리고 비교의 반복이죠.