2.실전 강의

2.1 Merge Sort

분할 정복 개념을 사용한 대표적인 정렬 알고리즘이며, 다음 순서에 따라 진행됩니다.

1. 정렬되지 않은 리스트를 절반으로 잘라 두 개의 리스트로 나눈다.
2. 생성된 두개의 리스트를 Merge Sort 알고리즘을 재귀 호출하여 정렬한다.
3. 정렬된 두개의 리스트를 다시 하나의 정렬된 리스트로 Merge한다.

Merge Sort는 항상 O(N∙logN) 의 시간 복잡도를 보장하기 때문에, 안정적인 수행속도가 보장되어야 할 때 많이 사용되며, 재귀 호출 방식으로 리스트를 계속하여 복사하기 때문에 정렬을 진행할 때 복사할 배열의 크기만큼 메모리 공간을 추가로 사용한다는 단점이 있습니다.

Merge Sort

int A[MAXN + 10];
int sorted[MAXN + 10];

void merge(int l,int m,int r) {
registerint i, j, k;
    i = l; j = m + 1; k = l;
while (i <= m && j <= r) {
if (A[i] <= A[j])
            sorted[k++] = A[i++];
else 
            sorted[k++] = A[j++];
    }

// 남아있는 값들 일괄 복사if (i > m) {
while (j <= r)
            sorted[k++] = A[j++];
    }
else {
while (i <= m)
            sorted[k++] = A[i++];
    }

// 배열 복사for (i = l; i <= r; i++)
        A[i] = sorted[i];
}

void mergeSort(int l,int r) {
int m;
if (l < r) {
        m = (l + r) / 2;
        mergeSort(l, m);
        mergeSort(m + 1, r);
        merge(l, m, r);
    }
}

2.2 Quick Sort

Quick Sort는 Merge Sort와 함께 분할 정복의 대표적인 정렬 알고리즘 이며, 다음 순서에 따라 진행됩니다.

1. 리스트 내에 임의의 원소를 선택하여 pivot이라 명합니다.
2. pivot을 기준으로 pivot보다 작은 원소는 좌측으로, pivot보다 큰 원소는 우측으로 이동합니다.
3. pivot을 제외하고 좌측 리스트와 우측 리스트를 Quick Sort 알고리즘을 재귀 호출하여 정렬합니다.
4. pivot으로 나눠진 리스트의 크기가 1이 될 때까지 반복합니다.

Merge Sort와 다르게 pivot이 어떻게 선택 되느냐에 따라 분할 횟수가 달라지며, 최악의 경우 O(N2)의 시간 복잡도를 가집니다. 하지만 평균적인 상황을 고려했을 때에는 O(N∙logN)의 시간 복잡도를 가지며, Median of three Quick Sort의 경우 최악의 경우에도 O(N∙logN)의 시간 복잡도로 정렬이 가능합니다. 또한 pivot이 이후 정렬의 대상에 포함되지 않기 때문에 다른 O(N∙logN)의 시간 복잡도를 가지는 정렬 중 대다수의 상황에서 가장 빠른 정렬이 가능합니다.

Quick Sort

void qsort(int l,int r) {
int s=l;int e=r;
int pivot = arr[(l+r)/2];

if(l >= r)return;

while(s <= e){
while(arr[s] > pivot) s++;
while(arr[e] < pivot) e--;
if(s <= e){
int temp;
            temp = arr[s];
            arr[s] = arr[e];
            arr[e] = temp;
            s++; e--;
        }
    }
    qsort(l,e);
    qsort(s,r);
}

2.3 Binary Search(이진탐색)

이진 탐색은 정렬 상태에서 특정 값을 O(logN) 의 시간 안에 찾을 수 있는 분할 정복 알고리즘 입니다. 실생활에서 볼 수 있는 가장 대표적인 예로, ‘업다운’ 이라는 게임을 예로 들 수 있습니다.

1~50 사이 임의의 숫자를 최소한의 기회로 맞추는 시나리오는 다음과 같습니다.

정답 : 17

위와 같이 탐색 대상의 중간 값을 호출하면서 반복할 때 마다 탐색 대상의 수를 절반으로 줄인다면 O(log2N)번의 탐색으로 원하는 값을 찾을 수 있습니다.

다만, 이진 탐색은 반드시 정렬이 선행되어 있어야 사용할 수 있습니다.

Binary Search

int binarySearch(int arr[],int s,int e,int target) 
{
	while (s <= e) 
	{
		int m = (s + e) / 2;
		if (arr[m] == target)
			return (m);
		elseif (arr[m] < target) 
			s = m + 1;
		else 
			e = m - 1;
	}
	return (-1);
}

int main() 
{
	int arr[4] = { 0, 1, 2, 3 };
	int ans = binarySearch(arr, 0, 3, 2);
	return 0;
}

Upper, lower bound를 구현 할 때, 실수를 방지하기 위해 ans라는 임시 변수를 사용한 예시입니다.

Upper Bound

int upperBound(int arr[],int s,int e,int target) 
{
	int ans = e + 1; // while loop 내부에서 ans가 갱신 되지 않았을 경우를 고려해 적절한 값으로 초기화
	while (s <= e) 
	{
		int m = (s + e) / 2;
		if (arr[m] > target) 
		{
			ans = m;
			e = m - 1;
		}
		else s = m + 1;
	}
	return ans;
}

Lower Bound

int lowerBound(int arr[],int s,int e,int target) 
{
int ans = e + 1;// while loop 내부에서 ans가 갱신 되지 않았을 경우를 고려해 적절한 값으로 초기화
while (s <= e) {
int m = (s + e) / 2;

if (arr[m] >= target) {
			ans = m;
			e = m - 1;
		}
else s = m + 1;
	}

return ans;
}

Index 배열을 추가하여 구조체 원본을 유지한채 정렬을 한 예시입니다.

이진 탐색도 같은 방식으로 처리 할 수 있습니다.

#include < stdio.h >#define MAXN 1000struct Node {
int data;

void myAlloc(int _data);
};

int bufferCnt;

Node buffer[MAXN];
int idxArr[MAXN];
int tempArr[MAXN];

void Node::myAlloc(int _data) {
	data = _data;
	idxArr[bufferCnt] = bufferCnt;
}

int myRand() {
staticunsignedint seed = 3423212;

	seed = seed * 42342233 + 34733355421;

return seed & 0xfffff;
}

void init() {
	bufferCnt = 0;

for (registerint i = 0; i < MAXN; i++) {
		buffer[bufferCnt].myAlloc(myRand());
		bufferCnt++;
	}
}

void printAll() {
for (int i = 0; i < MAXN; i++) {
int idx = idxArr[i];
		printf("%d:	%d\n", idx, buffer[idx].data);
	}
}

void mergeSort(int s,int e) {
if (s >= e)return;

int m = (s + e) / 2;

	mergeSort(s, m);
	mergeSort(m + 1, e);

int l, r, cur;

	l = cur = s, r = m + 1;

while (l <= m && r <= e) {
int leftIdx = idxArr[l], rightIdx = idxArr[r];
if (buffer[leftIdx].data <= buffer[rightIdx].data) tempArr[cur++] = idxArr[l++];
else tempArr[cur++] = idxArr[r++];
	}

while (l <= m) {
		tempArr[cur++] = idxArr[l++];
	}

while (r <= e) {
		tempArr[cur++] = idxArr[r++];
	}

for (int i = s; i <= e; i++) {
		idxArr[i] = tempArr[i];
	}
}

int main() {
	init();
	mergeSort(0, MAXN - 1);
	printAll();

return 0;
}