[알고리즘] 분할 정복(Divide and Conquer)

이번에는 분할 정복에 대해서 알아보려고 한다. 마찬가지로 알고리즘에서 수업했던 교재를 통해 복습했고 그 책 내용을 바탕으로 글을 써보려고 한다. 확실히 블로그에 글을 남기면서 복습이 되고, 나중에 기억이 안날때도 찾아보기가 쉬워서 더욱 자주 글을 쓰도록 해야겠다... 제발..

 

 분할 정복(Divide and Conquer) 이란, 문제의 입력 사례를 두 개 이상의 작은 입력 사례로 분할하는 것을 뜻한다. 딱 봐도 저번에 학습했던 DP 보단 훨씬 이해하기 쉬워보인다. 분할한 입력 사례의 답을 바로 얻을 수 있으면, 원래 문제의 답은 얻은 답들을 통합하여 구할 수 있다. 반면에, 답을 구하지 못하였다면, 더 작은 입력 사례로 다시 분할하고, 답을 구할 수 있을 만큼 충분히 작아질 때까지 분할을 계속 한다

 

정렬 알고리즘 중에서 퀵 정렬이나 합병 정렬과  이진 탐색, 선택 문제, 고속 푸리에 변환(FFT) 문제들이 대표적이다.

 

- 정렬 알고리즘 비교

	최고 성능	최악 성능	평균 성능
선택 정렬	O(n^2)	O(n^2)	O(n^2)
삽입 정렬	O(n^2)	O(n)	O(n^2)
합병 정렬(분할 정복)	O(nlogn)	O(nlogn)	O(nlogn)
퀵 정렬	O(n^2)	O(nlogn)	O(nlogn)

- 설계 전략

 1. Divide -> 문제의 입력 사례를 하나 이상의 작은 입력 사례로 분할한다.

 2. Conquer -> 작은 입력 사례들을 각각 푼다. 작은 입력 사례가 충분히 작지 않으면 재귀 호출.

 3. Combine -> 필요하다면, 작은 입력 사례의 해답을 통합하여 원래 입력사례의 해답을 구한다.

 

- 분할 정복 특징 및 장단점

* 특징 : Top-Down 방식으로 재귀 호출의 장단점과 유사

* 장점 : 코드가 직관적 + 병렬적으로 문제 접근

* 단점 : 재귀 호출로 오버 헤드 발생 가능 + 스택에 다량의 데이터가 보관되는 경우 오버플로우

 

- 병합 정렬

#include<iostream>

using namespace std;

int arr[10];
int arr2[10];

void merge(int left, int right)
{
	int mid = (left + right) / 2;

	int i = left;
	int j = mid + 1;
	int k = left;
	while (i <= mid && j <= right)
	{
		if (arr[i] <= arr[j])
			arr2[k++] = arr[i++];
		else
			arr2[k++] = arr[j++];
	}

	int tmp = i > mid ? j : i;

	while (k <= right) arr2[k++] = arr[tmp++];

	for (int i = left; i <= right; i++) arr[i] = arr2[i];
}

void divide(int left, int right)
{
	int mid;
	if (left < right)
	{
		mid = (left + right) / 2;
		divide(left, mid);
		divide(mid + 1, right);
		merge(left, right);
	}
}

int main() {
	int a;
	for (int i = 0; i < 10; i++) {
		cin >> a;
		arr[i] = a;
	}
	

	divide(0, 9);

	for (int i = 0; i < 10; i++) {
		cout << arr2[i] << " ";
	}

	
}