004_분할 정복

분할 정복

분할 정복 알고리즘(Divide and Conquer Algorithm) 이란 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 계산하고, 이를 병합해 문제를 해결하는 알고리즘이다.

분할 정복 알고리즘은 보통 재귀 함수를 통해 자연스럽게 구현되지만 함수 호출 오버헤드에 따른 실행 속도의 저하를 피하기 위해 재귀 함수를 이용하지 않고 스택, 큐 등의 자료구조를 이용해 구현할 수 도 있다.

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

예시

수열의 합

1 부터 N 까자의 값을 분할 정복을 통해 구하면 다음과 같다.

#include <iostream>

int Sum(int N)
{
	if (1 == N)
		return N;
	else
		return N + Sum(N - 1);
}

int main() 
{
	std::cout << Sum(10);
	return 0;
}

그러나 위의 방식의 경우 N 값이 5000 정도만 넘어도 스택 오버플로우가 발생한다. 다른 방법으로 프로그램을 구현하기 위해 식을 변형해본다.

1 + 2 + 3 + 4 + 5 + 6 + 7 + 8
= (1 + 2 + 3 + 4) + (5 + 6 + 7 + 8)
= (1 + 2 + 3 + 4) + (4 * 4) + (1 + 2 + 3 + 4)
= 2 * (1 + 2 + 3 + 4) + (4 ^ 2)

위 식을 같은 방식으로 일반화 해보면 아래와 같다.

1 + 2 + 3 + 4 + ... + N
= (1 + 2 + 3 + 4 + ... + N / 2) + {(N / 2 + 1) + (N / 2 + 2) + (N / 2 + 3) + ... + (N / 2 + N / 2)}
= (1 + 2 + 3 + 4 + ... + N / 2) + {(N / 2) * (N / 2)} + (1 + 2 + 3 + 4 + ... + N / 2)
= 2 * (1 + 2 + 3 + 4 + ... + N / 2) + (N / 2) ^ 2

문제를 보면 1 + 2 + 3 + 4 + … + N 을 구하는 문제가 1 + 2 + 3 + 4 + … + N/2 로 바뀌었음을 볼 수 있다. 이는 다시 1 + 2 + 3 + 4 + … + N/4 로 쪼갤 수 있고, 계속해서 쪼개나가면 문제를 점점 작은 조각 으로 자를 수 있다.

참고로 위 식은 짝수일 경우만 적용되며, 홀수일 경우에는 N - 1 까지의 합을 구하고 N을 더하는 식으로 문제를 해결할 수 있다.

#include <iostream>

int FastSum(int N)
{
	if (1 == N)
		return N;
	else
	{
		if (0 == N % 2)
			return 2 * FastSum(N / 2) + (N / 2) * (N / 2);
		else
			return 2 * FastSum((N - 1) / 2) + ((N - 1) / 2) * ((N - 1) / 2) + N;
	}
}

int main() 
{
	std::cout << FastSum(50000);
	return 0;
}

1250025000

병합 정렬

분할 정복을 통해 병합 정렬을 구현할 수 있다. 병합 정렬의 과정은 아래와 같다.

2개씩 묶일 때까지 반으로 나눈다.
각 요소들을 정렬하며 두 묶음이 될 때 까지 합쳐나간다.
2번 에서 나온 두 묶음에서 맨 앞을 비교해 크기가 작은 요소를 가져와 배치한다.

#include <iostream>
#include <vector>

void Merge(std::vector<int>& V, std::vector<int>& Temp, int Left, int Right)
{
	// 정렬
	int Mid = (Left + Right) / 2;
	int IdxL = Left, IdxR = Mid + 1, Idx = Left;
	while (IdxL <= Mid && IdxR <= Right)
	{
		if (V[IdxL] <= V[IdxR])
			Temp[Idx++] = V[IdxL++];
		else
			Temp[Idx++] = V[IdxR++];
	}

	// 남은 요소 처리
	int Remain = (IdxL <= Mid) ? IdxL : IdxR;
	while (Idx <= Right)
		Temp[Idx++] = V[Remain++];

	// 복사
	for (int i = Left; i <= Right; ++i)
		V[i] = Temp[i];
}

void Divide(std::vector<int>& V, std::vector<int>& Temp, int Left, int Right)
{
	if (Left < Right)
	{
		int Mid = (Left + Right) / 2;
		Divide(V, Temp, Left, Mid);
		Divide(V, Temp, Mid + 1, Right);
		Merge(V, Temp, Left, Right);
	}
}

void MergeSort(std::vector<int>& V)
{
	std::vector<int> Temp(V.size(), 0);
	Divide(V, Temp, 0, V.size() - 1);
}

int main() 
{
	std::vector<int> Vec = { 3, 1, 4, 8, 6, 2, 5, 7, 9 };

	std::cout << "정렬 전 : ";
	for (int Num : Vec)
		std::cout << Num << " ";

	MergeSort(Vec);

	std::cout << "\\n정렬 후 : ";
	for (int Num : Vec)
		std::cout << Num << " ";

	return 0;
}

정렬 전 : 3 1 4 8 6 2 5 7 9
정렬 후 : 1 2 3 4 5 6 7 8 9