[알고리즘]#4_분할-정복 알고리즘

 

[알고리즘]#4_분할-정복 알고리즘

 

분할-정복 알고리즘에 대해 알아보겠습니다.

 

---

 

Overview

 

1. 개념
2. 예제

 

#0. 개념

1. 분할 정복 알고리즘

• 분할 정복 알고리즘은 먼저 전체 문제를 원래 문제와 유사하지만 크기가 더 작은 몇 개의 부분 문제로 "분할"하여 재귀적으로 해결합니다. 그리고, 분할된 부분 문제들에서 찾은 해를 결합하여 원래 문제의 해를 찾아내는 알고리즘 방법론입니다.
• 일반적으로, 분할-정복 알고리즘은 다음 세 가지 단계로 구성됩니다. (1) 분할 : 현재 문제를 같은 문제를 다루는 다수의 부분 문제로 분할한다.(2) 정복 : 이렇게 분할된 부분 문제들을 재귀적으로 해결합니다. 분할된 부분 문제들의 크기가 충분히 작다면(Base Case) 직접적인 방법으로 해를 찾아냅니다. (3) 결합 : 부분 문제들의 해를 결합하여 원래 문제의 해답을 얻습니다. 

 

#1. 예제

1. 병합 정렬

#include <iostream>
#include <vector>
using namespace std;

void MergeSort(vector<int>& arr, int Left, int Right);
void Merge(vector<int>& arr, int Left, int Mid, int Right);
 
void MergeSort(vector<int>& arr, int Left, int Right)
{

	if (Left < Right)
	{
		int Mid = (Left + Right) / 2;

		// #1. 두 부분 배열에 대해 재귀 호출
		MergeSort(arr, Left, Mid);
		MergeSort(arr, Mid + 1, Right);

		// #2. 두 부분 배열을 병합하는 함수
		Merge(arr, Left, Mid, Right);
	}

}

void Merge(vector<int>& arr, int Left, int Mid, int Right)
{
	int LeftSize = Mid - Left+1;
	int RightSize = Right - Mid;

	// #3. 두 부분 배열을 저장할 임시 배열
	vector<int> Left_Half(LeftSize);
	vector<int> Right_Half(RightSize);

	for (int i = 0; i < LeftSize; i++)
	{
		Left_Half[i] = arr[Left + i];
	}

	for (int i = 0; i < RightSize; i++)
	{
		Right_Half[i] = arr[Mid + i + 1];
	}

	int Left_Idx = 0;
	int Right_Idx = 0;
	int Res_Idx = Left;

	// #4. 왼쪽 부분 배열과 오른쪽 부분 배열의 원소들을 차례대로 비교하여, 하나의 배열로 병합 
	while (Left_Idx < LeftSize && Right_Idx < RightSize)
	{
		if (Left_Half[Left_Idx] <= Right_Half[Right_Idx])
		{
			arr[Res_Idx] = Left_Half[Left_Idx];
			Left_Idx++;
		}
		else
		{
			arr[Res_Idx] = Right_Half[Right_Idx];
			Right_Idx++;
		}
		Res_Idx++;
	}

	// #5. 위 작업 과정에서 남은 한 부분 배열의 원소들을 병합 배열 뒤에 추가
	while (Left_Idx < LeftSize)
	{
		arr[Res_Idx] = Left_Half[Left_Idx];
		Left_Idx++;
		Res_Idx++;
	}

	while (Right_Idx < RightSize)
	{
		arr[Res_Idx] = Right_Half[Right_Idx];
		Right_Idx++;
		Res_Idx++;
	}

}


int main()
{

	vector<int> arr = { 38, 27, 43, 3, 9, 82, 10 };

	MergeSort(arr, 0, arr.size() - 1);

	for (int i = 0; i < arr.size(); i++)
	{
		cout << arr[i] << '\n';
	}


	return 0;
}

 

Details

 

[알고리즘]#3_정렬 알고리즘

 

• 병합 정렬 알고리즘은 "분할-정복 알고리즘"을 활용한 대표적인 예입니다.
• 병합 정렬 알고리즘은 주어진 배열을 두 개의 작은 부분 배열로 분할하고, 각 부분 배열을 재귀적으로 정렬하여, 최종적으로 두 배열을 결합하여 하나의 정렬된 배열을 얻는 정렬 알고리즘입니다.

 

2. 퀵 정렬

#include <iostream>
#include <vector>
using namespace std;

void QuickSort(vector<int>& arr, int l, int r);
int Partition(vector<int>& arr, int l, int r);

void QuickSort(vector<int>& arr, int l, int r)
{
	if (l < r)
	{
		int Pivot = Partition(arr, l, r);

		QuickSort(arr, l, Pivot-1);
		QuickSort(arr, Pivot + 1, r);
	}
}

int Partition(vector<int>& arr, int l, int r)
{
	// #1. Pivot 값은 arr[r] 값으로 설정
	int Pivot = arr[r];
	int i = l - 1;

	for (int j = l; j < r; j++)
	{
		// #2. 배열을 순회하며 Pivot 값보다 작으면, i인덱스와 위치 변경
		if (arr[j] <= Pivot)
		{
			i++;
			swap(arr[j], arr[i]);
		}
	}

	// #3. 왼쪽 부분 배열(Pivot 값 보다 작은 값들 | Pivot 위치 | 오른쪽 부분 배열(Pivot 값 보다 큰 값들
	swap(arr[i+1], arr[r]);

	return i + 1;

}

int main()
{

	vector<int> arr = { 38, 27, 43, 3, 9, 82, 10 };

	QuickSort(arr, 0, arr.size() - 1);

	for (int i = 0; i < arr.size(); i++)
	{
		cout << arr[i] << '\n';
	}


	return 0;
}

 

Details

 

 

[알고리즘]#3_정렬 알고리즘

 

• 퀵 정렬 알고리즘 또한 "분할-정복" 알고리즘의 대표적인 예입니다.
• 퀵 정렬 알고리즘은 배열의 Pivot 원소를 기준으로 Pivot의 왼쪽에 위치한 원소들은 Pivot값 보다 작은 값들, 반대로 오른쪽에 위치한 원소들은 Pivot 값보다 큰 원소들로 나눕니다. 이렇게 나누어진 두 개의 작은 부분 배열에 대해 재귀적으로 정렬 작업을 수행하고, 최종적으로 정렬된 하나의 배열을 얻습니다.