[알고리즘] 선택 문제 (selection_merge)

선택 문제 (selection)

n개의 숫자들 중에서 k번째로 작은 숫자를 찾는 문제.

효율적으로 찾기 위해 분할 정복 개념 씀.

수도코드 및 시간복잡도

selection(A, left, right, k)
입력 : A[left]~A[right]와 k (단, 1<= k <=|A| , |A| = right-left+1)
출력 : A[left]~A[right]에서 k번째 작은 원소

피봇을 A[left] ~ A[right] 중에 선택하고, 피봇을 A[left]와 자리를 바꾼 후,
피봇과 배열의 각 원소를 비교하여 피봇보다 작은 숫자들은 A[left] ~ A[p-1]로 옮기고,
피봇보다 큰 숫자들은 A[p+1] ~ A[right]로 옮기며, 피봇은 A[p]에 놓는다.

S = (p-1)-left+1 //S = small group의 크기
if(k <= S) selection(A, left, p-1 ,k) //small group에서 찾기
else if (k = S+1) return A[p] //피봇 = k 번째 작은 숫자
else selection(A,p+1,right,k-S-1) //large group에서 찾기

퀵 정렬 후, 나누어진 두 부분 문제(배열)에 대해 k번째 원소가 있는 부분 문제 하나를 택하여 과정을 반복한다.

• 피봇이 입력을 small group , large group으로 분할하고, 두 그룹 중의 하나의 크기가 입력 크기의 3/4와 같거나 그보다 크게 분할하면 bad 분할이라고 정의하자. good 분할은 두 그룹의 크기가 모두 입력 크기의 3/4보다 작은 경우이다.
• 피봇을 랜덤하게 정했을 때 good 분할이 될 확률이 1/2 이므로, 평균 2회 연속해서 랜덤하게 피봇을 정하면 good 분할을 할 수 있다. => good 분할만 연속하여 이루어졌을때 시간복잡도 x2 = 평균 시간복잡도

 

• 처음 입력의 크기가 n일때, 두 그룹으로 분할되는데 소요되는 시간 = O(n)
• 분할 후 큰 부분의 최대 크기는 (3/4 n -1) -> 편의상 3/4n 이라 두자.
• 2번째 분할은 (3/4)^2n 보다 작고, 3번째 분할은 (3/4)^3n 보다 작다.
• O[n + 3/4n + (3/4)^2n + (3/4)^3n + (3/4)^4n + (3/4)^5n + .... + (3/4)^in] = O(n)
• 2xO(n) = O(n)

정렬을 하지 않고 k번째 작은 수를 선형 시간에 찾을 수 있게해줌.

 

---

교재 문제 5 ) P.100

section(A, 4, 9, 2)이므로 찾으려는 수는 7번째로 작은 수 이다. 따라서, 오른쪽 부분에서는 2번째 작은 수를 찾아야 한다.

교재 문제 16 ) P.101

피봇이 입력 배열을 너무 한쪽으로 치우치게 분할하는 경우는 피봇의 해당하는 수가 작은 경우이다. 따라서, 나누어지는 부분문제 중 크기가 큰 배열이 생겨, 또다른 피봇을 기준으로 정렬할 때, 여러번 퀵 정렬을 해야하므로 횟수가 많아진다. 따라서 알고리즘 수행 시간이 길어진다.

코드 (c++)

/*
selection(A, left, right, k)
입력 : A[left]~A[right]와 k (단, 1<= k <=|A| , |A| = right-left+1)
출력 : A[left]~A[right]에서 k번째 작은 원소

피봇을 A[left] ~ A[right] 중에 선택하고, 피봇을 A[left]와 자리를 바꾼 후,
피봇과 배열의 각 원소를 비교하여 피봇보다 작은 숫자들은 A[left] ~ A[p-1]로 옮기고,
피봇보다 큰 숫자들은 A[p+1] ~ A[right]로 옮기며, 피봇은 A[p]에 놓는다.

S = (p-1)-left+1 //S = small group의 크기
if(k <= S) selection(A, left, p-1 ,k) //small group에서 찾기
else if (k = S+1) return A[p] //피봇 = k 번째 작은 숫자
else selection(A,p+1,right,k-S-1) //large group에서 찾기
*/
#include <iostream>
#include <vector>
using namespace std;
int K;

void swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}
int partition(vector<int>& a, int left, int right)
{
	int x = a[right];
	int i = left - 1;
	for (int f = i + 1; f < right; f++)
	{
		if (a[f] <= x)
			swap(&a[++i], &a[f]);
	}
	swap(&a[right], &a[i+1]);

	return i + 1;
}
int selection(vector<int>& a, int left, int right, int k)
{
	int p;
	int S;
	if (left < right)
	{
		p = partition(a, left, right);
		S = (p - 1) - left + 1;//smallgroup 크기
		if (k <= S)
			selection(a, left, p - 1, k);//smallgroup
		else if (k == S + 1)
			return a[p];
		else
			selection(a, p + 1, right, k - S - 1);//largegroup 

	}
}
int main() {
	cin >> K;
	vector<int> a = { 6,3,11,9,12,2,8,15,18,10,7,14 };
	int left = 0;
	int right = a.size() - 1;
	int result = selection(a, left, right, K);
	cout << result << endl;
	return 0;
}

---