Selection Problem 선택 알고리즘
Q. n개의 원소 중 k번째로 큰 숫자는 무엇인가?
{45, 33, 21, 5, 6, 8, 63, 54, 76, 82}
선택 알고리즘이란 다음과 같은 문제가 주어졌을 때, O(n) 시간 복잡도를 가지는 풀이법이다.
선택 알고리즘을 설명하기에 앞서, 다른 방식으로 문제를 해결할 때의 시간 복잡도를 확인해보자.
방법1. 가장 큰 숫자를 찾고, 그 숫자를 제외한 나머지에서 가장 큰 숫자를 찾고, ... 이를 반복하는 방법.
- k번째 큰 숫자를 찾을 때?
1번째 큰 수는 n번의 비교,
2번째 큰 수는 n-1번의 비교,
...
k번째 큰 수는 n-(k-1)번 비교 => 따라서, O(kn)
- k=1번째 큰 수는 O(n)
- k=n번째 큰 수는 O(n^2)
방법2. 모든 수를 정렬하고 k번째 숫자를 결정하는 방법.
정렬할 때, Bubble, insert등의 sort를 사용하면 O(n^2)를 가지고,
Quick, Selection sort를 사용하면 O(nlogn)의 시간복잡도를 가진다.
그러나 이 방법은 불필요한 부분까지 정렬을 하게되고 지금 하게 될 선택 알고리즘보다 느리다.
개념
선택 알고리즘은 Quick sort에서 pivot이 자리를 결정하는 과정을 응용한 방법이다.
pivot이 자신의 자리를 찾아가고 원소의 갯수가 n/2으로 나눠지면서 그 절반만(혹은 절반보다 큰 양) 확인을 해보면 된다.
따라서 O(n)의 시간복잡도를 가진다.
예시.
{45, 33, 21, 5, 6, 8, 63, 54, 76, 82} 에서 k=4번째로 큰 수는 무엇인가?
1. 첫 번째 원소인 pivot이 자신의 위치를 찾아간다.
2. pivot이 6번째 위치로 옮겨가고, pivot을 기준으로 왼쪽만 확인하면 된다. (k=4 < pivot=6)
3. 왼쪽 부분 배열에서 pivot을 새로 선정하고, 자신의 위치를 찾아간다.
4. pivot이 3번째 위치로 옮겨가고, pivot을 기준으로 오른쪽만 확인하면 된다. (k=4 > pivot=3)
오른쪽 부분 배열에서 pivot을 새로 선정하고, 자신의 위치를 찾아가는데, 자신의 위치가 4이다.(찾으려는 숫자)
끝~
시간 복잡도 계산
pivot에 의해 나눠지는 2개 부분이 원래 길이의 3/4 미만이 될 때, good division임. -> 근데 이유모르겠음
c언어 구현 코드
#include <stdio.h>
#define SZ 10
int numbers[SZ] = {45,33,21,5,6,
8,63,54,76,82};
// _which : 찾고자 하는 숫자의 index -> _which번째 큰 수
void doSelection(int _pivot, int _left, int _right, int _which) {
// 탈출조건
if ( (_pivot <0 || _pivot>=SZ) ||
(_left <0 || _left >= SZ) ||
(_right <0 || _right >= SZ)) {
printf("exit:: found location %d, which is %d\n", _which+1, numbers[_which]);
return;
}
// 기본적인 quick sort
int left = _left;
int right = _right;
while (1) {
// left를 이동 : pivot보다 작은 숫자들을 skip
while (numbers[_pivot] > numbers[left]) {
left++;
}
// right를 이동 : pivot보다 큰 숫자들을 skip
while (numbers[_pivot] < numbers[right]) {
right--;
}
// left와 right의 자리를 바꿔준다.
if (left < right) {
int temp = numbers[left];
numbers[left] = numbers[right];
numbers[right] = temp;
}
else {
if (right==_which) { // 내가 찾고자 하는 위치 which가 right와 동일
printf("found %d number is %d\n",right+1,numbers[_pivot]);
return;
}
else {
// 일단 pivot과 right의 위치를 바꾸고
int temp = numbers[_pivot];
numbers[_pivot] = numbers[right];
numbers[right] = temp;
// 내가 찾고자하는 _which가 right의 왼쪽인지, 오른쪽인지 검사
if (_which < right) { // 왼쪽 부분 배열만 확인하면 된다.
doSelection(_pivot,_pivot+1,right-1,_which);
}
else { // 오른쪽 부분 배열만 확인하면 된다.
doSelection(right+1,right+2,_right,_which);
}
return;
}
}
}
}
int main(void) {
doSelection(0, 1, SZ - 1, 3); // 4번째로 큰수 -> 인자 3
return 0;
}
doSelection()함수의 가장 첫 부분 탈출조건에서 k번째 수를 출력해주는 이유?
탈출조건에 doSelection 함수가 들어온 경우는 내가 찾는 k번째 수가 포함된 부분배열이 모두 정렬되었다는 의미이다.
따라서 바로 배열의 k인덱스로 참조하여 출력할 수 있다.
예시) 아래와 같은 원소들 중에서, k=10번째 수는?
doSelection의 함수인자 중에서 left가 배열사이즈를 넘어가기때문에 탈출조건에 들어간다.
