[SWEA] 21. 분할 정복
2.실전 강의
2.1 Merge Sort
분할 정복 개념을 사용한 대표적인 정렬 알고리즘이며, 다음 순서에 따라 진행됩니다.
- 정렬되지 않은 리스트를 절반으로 잘라 두 개의 리스트로 나눈다.
- 생성된 두개의 리스트를 Merge Sort 알고리즘을 재귀 호출하여 정렬한다.
- 정렬된 두개의 리스트를 다시 하나의 정렬된 리스트로 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와 함께 분할 정복의 대표적인 정렬 알고리즘 이며, 다음 순서에 따라 진행됩니다.
- 리스트 내에 임의의 원소를 선택하여 pivot이라 명합니다.
- pivot을 기준으로 pivot보다 작은 원소는 좌측으로, pivot보다 큰 원소는 우측으로 이동합니다.
- pivot을 제외하고 좌측 리스트와 우측 리스트를 Quick Sort 알고리즘을 재귀 호출하여 정렬합니다.
- 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
25 | Down |
---|---|
12 | Up |
18 | Down |
15 | Up |
16 | Up |
17 | Correct |
위와 같이 탐색 대상의 중간 값을 호출하면서 반복할 때 마다 탐색 대상의 수를 절반으로 줄인다면 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;
}
Author And Source
이 문제에 관하여([SWEA] 21. 분할 정복), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@24siefil/SWEA-21.-분할-정복저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)