Divide and Conquer ( 분할 정복 )

✔️ 분할 정복

◾ 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산하는 알고리즘 기법

◾ 분할 정복은 대개 아래와 같이 3가지의 구성요소를 가지고 있다.

◾ 문제를 더 작은 문제로 분할하는 과정(Divide)

◾ 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정(Merge)

◾ 더 이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제(Base Case)

 

---

✔️ Binary Seach(이분 탐색)

◾ 정렬되어 있는 리스트에서 어떤 값을 빠르게 찾는 알고리즘

⏱️ 시간 복잡도

◾ 탐색 : 리스트의 크기가 N일때 O(logN)의 시간이 걸린다. 

 

💾 소스 코드

 

int binarySearch(int num, int left, int right) {
	while (left <= right) {
		int mid = (left + right) / 2;
		if (arr[mid] == num) //arr에 num이 존재한다면, index 반환
			return mid;
		else if (arr[mid] > num) {
			right = mid - 1;
		}
		else if (arr[mid] < num) {
			left = mid + 1;
		}
	}
	return -1; //arr에 num이 존재하지 않는다면, -1 반환
}

 

👀 시각화

이분탐색 시각화

 

 

---

✔️ Merge Sort(병합 정렬)

◾ Merge Sort는 분할정복 기법을 사용하는 정렬 알고리즘이다. 

◾ 전체 정렬 대상을 여러 부분 집합으로 분할하고(Divide) 각 부분 집합에 대해 정렬 작업을 수행한 후에(Conquer) 정렬된 부분 집합들을 다시 결합하는(Combine) 분할 정복 기법을 사용한다.

◾ 분할(Divide) : 원소들을 같은 크기의 부분집합 2개로 분할한다. 부분 집합의 크기가 충분히 작지 않으면 재귀 호출을 이용하여 다시 계속 분할한다. 

◾ 정복(Conquer) : 부분집합에 있는 원소들을 정렬한다. 

◾ 결합(Combine) : 정렬된 각 부분 집합들을 하나의 정렬된 집합으로 결합한다.

◾ "8개의 데이터를 정렬하는 것 보다 이를 둘로 나눠서 4개의 데이터를 정렬하는 것이 더 쉽고 또 이들 각각을 다시 한번 둘로 나눠서 2개의 데이터를 정렬하는 것이 더 쉽다. "

 

⏱️ 시간 복잡도

◾ Merge Sort는 N개의 원소를 O(logN)번 분할하고, 분할된 각 부분 집합의 원소들을 정렬하면서 병합하는 단계에서 최대 N번의 비교 연산을 수행한다. 따라서 총 시간 복잡도는 O(NlogN)이 된다.

◾ Merge Sort의 시간복잡도는 최악, 평균, 최선의 경우에 상관없이 O(NlogN)이다. (항상 2분할을 하기 때문)

◾ Merge Sort는 부분 집합을 병합하는 과정에서 임시 메모리가 추가적으로 필요하다는 단점이 있다. (하지만 정렬 대상이 배열이 아닌 연결 리스트일 경우는 단점이 되지 않음)

 

💾 소스 코드

#include<iostream>
using namespace std;

int a[10], b[10]; // 배열 b는 Merge Sort에서 추가적으로 필요한 임시 메모리 공간이다.

void merge(int start, int end) { 
	int mid = (start + end) / 2;
	int i = start, j = mid + 1, k = 0;

	while (i <= mid && j<=end){
		if (a[i] <= a[j])
			b[k++] = a[i++];
		else
			b[k++] = a[j++];
	}

	while (i <= mid) b[k++] = a[i++];
	while (j <= end) b[k++] = a[j++];

	for (int i = start; i <= end; i++) {
		a[i] = b[i - start];
	}
}

void sort(int start, int end) {
	if (start == end) {
		return;
	}

	int mid = (start + end) / 2;
	sort(start, mid);
	sort(mid + 1, end);
	merge(start, end);
}


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

	sort(0, 9);

	for (int i = 0; i < 10; i++) {
		printf("%d ", a[i]);
	}

	return 0; 
}

👀 시각화

Merge Sort 과정

 

---

Merge Sort 시각화

---

✔️ Quick Sort(퀵 정렬)

◾ Quick sort도 Merge Sort와 마찬가지로 분할정복 기법을 사용하는 정렬 알고리즘이다. 

◾ 평균적으로 매우 빠른 정렬 속도를 보인다.

◾ Quick sort는 정렬할 원소들중 하나를 pivot을 지정하고 그 pivot을 기준삼아 정렬을 진행한다. 

 

💭퀵 정렬의 과정

 

그림 (a)

- 그림 (a)는  퀵 정렬의 대상이 되는 배열을 보여준다.

 

    ◾ left : 정렬대상의 가장 왼쪽 지점을 가리키는 이름

    ◾ right : 정렬대상의 가장 오른쪽 지점을 가리키는 이름

    ◾ pivot : 정렬을 진행하는데 필요한 기준

    ◾ low : 피벗을 제외한 가장 왼쪽에 위치한 지점을 가리키는 이름

    ◾ high : 피벗을 제외한 가장 오른쪽에 위치한 지점을 가리키는 이름

 

- 본격적으로 퀵 정렬의 과정을 살펴보자. 오름차순을 기준으로, low는 피벗보다 큰 값을 만날 때까지 오른쪽 방향으로 이동하고, high는 피벗보다 작은 값을 만날 때까지 왼쪽 방향으로 이동한다.  그러면 그림 (b)와 같은 상태가 된다.

 

그림 (b)

- 그 다음 low와 high를 교환한다. 그러면 그림 (c)와 같은 상태가 된다. 

그림 (c)

- 7과 4의 교환 후에도 계속해서 low는 오른쪽으로, high는 왼쪽으로 이동한다. 마찬가지로 low는 피벗보다 큰 값을 찾고, high는 피벗보다 작은 값을 찾는다. 따라서 low와 high는 각각 9와 2를 가리키고, 이번에도 이 둘을 교환하여 그림 (d)의 상태가 되게 한다.

 

그림 (d)

- 이후에도 low는 피벗보다 큰 값을 찾을 때까지 오른쪽으로, high는 피벗보다 작은 값을 찾을 때까지 왼쪽으로 이동한다. 그러면 결국 그림 (e)와 같이 low와 high가 가리키는 위치가 교차되는 상황이 발생한다.

 

그림 (e)

 

- 이렇게 low와 high가 교차되는 상황은 이동 및 교환의 모든 과정이 완료되었음을 의미한다. 따라서 이번에는 피벗과 high가 가리키는 데이터를 서로 교환하여 그림 (f)의 상태가 되게 한다.

 

그림 (f)

- 그림 (f)를 유심히 보자. 피벗의 왼편에는 피벗보다 작은 값들이 위치하고, 피벗의 오른편에는 피벗보다 큰 값들이 위치한다. 따라서 피벗이었던 5는 정렬되었을 때의 제 위치를 찾았다. 피벗이었던 숫자 5는 홀로 정렬이 완성되었다.

 

그림 (g)

- 제자리를 찾은 5를 기준으로 왼쪽 영역과 오른쪽 영역을 대상으로 지금까지 설명한 과정을 재귀적으로 반복하면 정렬이 완성된다. 

 

⏱️ 시간 복잡도

◾ Quick Sort는 pivot 선택에 따라 성능이 달라진다. 전체 데이터를 기준으로 중간에 해당하는 값을 pivot으로 결정할 때 좋은 성능을 보인다. pivot이 중간에 해당하는 값을 경우, 정렬 대상은 균등하게 나뉘기 때문이다.

◾ 중간에 가까운 pivot을 선택하면 평균적으로 O(NlogN)의 시간이 걸린다.

◾ 하지만 pivot을 적절히 설정하지 않으면 최악의 경우 O(N^2)의 시간이 걸린다.

◾ Big O 표기는 최악의 경우를 구하는 것 아닌가? -> Quick 정렬의 경우에는 약간의 예외를 둔다.

◾ 최대한 중간 값에 가까운 pivot을 선택하기 위해 정렬대상에서 3개의 데이터를 추출한다음 그 중에서 중간 값에 해당하는 것을 pivot으로 선택한다.

◾ Quick Sort는 다른 정렬 알고리즘과 비교했을 때에도 평균적으로 제일 빠른 것으로 알려져 있다.

◾ Quick 정렬은 데이터 이동횟수가 상대적으로 적고, Merge Sort와 같이 별도의 메모리 공간을 요구하지 않으므로 동일한 시간복잡도를 갖는 다른 정렬 알고리즘 중에서 평균적으로 가장 빠른 정렬 속도를 보인다. 

 

👀 시각화

Quick Sort 시각화

💾 소스 코드