[알고리즘 / 분할정복] #3 선택 문제 (Quick-Selection)

 

선택 문제 (Quick-Select)

💡 크기가 n인 배열에서 k번째로 작은 수를 찾는 문제이다.

 

간단한 해결책

 

선택문제는 크기가 n인 배열에서 몇 번째로 작은 수를 찾는 탐색을하는 알고리즘을 말한다.

이런 문제는 다음과 같은 간단한 방법도 있다.

 

1. 최소 숫자를 k번 찾는다. (배열을 순차적으로 다 찾는다는 말이다.) 단, 최소 숫자를 찾은 뒤에는 입력에서 그 숫자를 제거한다. O(kn)
   1. 크기가 10인 배열에서 3번째로 작은 수를 찾는다.
   2. 10개의 배열을 다 확인하여 최소 수를 찾고 배열에서 제외한다.
   3. 2번 작업을 3번 반복하여 3번째 최소 숫자를 찾는다.
2. 숫자들을 오름차순으로 정렬(O(nlogn))한 후, k번째 숫자를 찾는다. O(nlogn)
   1. 크기가 10인 배열에서 3번쨰로 작은 수를 찾는다.
   2. 배열을 오름차순으로 정렬한다. O(nlogn)
   3. 배열의 3번째 원소를 반환한다.

하지만, 두 경우 모두 최악의 경우 수행시간이 길어지며 이보다 효율적인 해결을 위해 분할 정복 개념을 활용한다.

 

 

 

이진탐색(퀵정렬) 해결책

임의의 숫자를 효율적으로 찾는 이진탐색(Binary Search)를 통해 정렬된 입력의 중간에 있는 숫자와 찾고자하는 숫자를 비교하여 입력을 1/2로나눈 두 부분 중 탐색에 유효한 숫자가 있는 쪽만 검색한다.

 

선택 문제는 입력이 정렬되어 있지 않은 상태이다.

 

이를 퀵 정렬과 같이 정렬하여 피봇을 기점으로 분할한다.

이때, 그룹의 크기(배열의 크기)를 알고 있어야 목표 값이 어느 그룹에 있는고 해당 그룹에 몇 번째 작은 수를 찾아야하는지 알 수 있다.

 

 

 

---

시간복잡도

 

선택문제의 시간복잡도를 구하기 위해서는 선택문제에서 발생하는 2가지 분할 결과를 알아야한다.

 

선택문제 알고리즘은 분할 정복 알고리즘이면서 랜덤(random) 알고리즘이다.

이는 피봇을 랜덤하게 정하여 정렬을 먼저하기 때문이며 만일 피봇이 한 쪽으로 치우치는 분할일 경우 알고리즘 수행 시간이 길어진다.

 

 

이렇게 한 쪽으로 치우치는 확률은 1/2확률로 볼 수 있고 이러한 기준은 다음과 같다.

1. 어느 한쪽의 배열의 크기가 3/4 이상이면 Bad(나쁜) 분할
2. 나누어진 두 배열 모두 크기가 3/4 미만이면 Good(좋은) 분할

피봇을 랜덤하게 정할 때 good 분할이 될 확률은 1/2이므로 평균 2회 연속 랜덤한 피봇을 정하면 good 분할을 할 수 있다.

 

즉, 매 2회마다 good 분할이되고 good 분할만 연속하여 이루어졌을 때만 시간복잡도를 구하여 그 값에 2를 곱하면 평균 경우 시간복잡도가 구해진다.

 

 

ex) 시간복잡도 예시

• 첫번째 분할 크기가 n인 배열에 피봇을 랜덤하게 선택 피봇을 기준으로 두 그룹으로 분할 O(n)
  • 분할 후 큰 배열의 크기는 good 분할만 일어난다는 가정하에 3/4보다 작은 ((4/3) * n) - 1)이다. ​
  • 편의상 다음 공식으로 변경 가능 =>

 

• 두번째 분할
  • 큰부분 크기는 3/4보다는 작은 (3/4)n이고, 이를 두 그룹으로 분할하면, 분할 시간은 O((3/4)n)이다.
  • 분할 후 큰 배열의 최대 크기는 ((3/4)((3/4)n) = (3/4)^2 * n보다 작다.

 

• 세번째 분할 큰부분 크기는 ((3/4)^2 * n)이고, 이를 두 그룹으로 분할하면, 분할 시간은 O((3/4)^2 * n)$이다.
  • 분할 후 큰 배열의 최대 크기는 (3/4)(3/4)^2 * n = (3/4)^3 * n보다 작다.

 

• ...

 

• i번째 분할
  • 크기가 (3/4)^(i-1) * n인 부분을 두 그룹으로 분할하는데 걸리는 시간은 O((3/4)^(i-1) * n)이다.
  • 분할 후 큰 배열의 최대 크기는 (3/4)(3/4)^(i-1) * n = (3/4)^i * n보다 작다.

 

즉, 입력 크기 n에서 3/4배로 연속적 감소하고, 입력 크기가 1일 때는 더 이상 분할할 수 없다.

그러므로 선택문제 알고리즘의 평균 경우 시간복잡도는 다음과 같다.

 

 

결국, 평균 시간 복잡도는 2*O(n) = O(n)이다. (2를 곱한 이유는 평균 2번 만에 good분할이 되기 때문)

 

---

특징

1. 선택문제 알고리즘은 이진탐색과 매우 유사하여 분할 과정을 진행하며 탐색 범위를 반씩 줄이고 부분문제들을 취합하는 과정도 필요 없다.
2. 정렬을 하지 않고 k번째 작은 수를 선형 시간에 찾을 수 있도록 해준다.
3. 데이터 분석을 위한 중앙값(median)을 찾는 데 활용된다.

 

---

코드 예제

💡 수도코드

/// <data1 : int A[]>     정렬해야하는 배열
/// <data2 : int left>    배열의 시작점
/// <data3 : int right>   배열의 끝점
/// <data4 : int k>       찾는 자릿 수
Selection(A, left, right, k)
입력 : 배열 A[left]~A[right]와 k. 단, 1 <= k <= |A|, |A|=right-left-1
출력 : 정렬된 배열 A[left]~A[right]에서 k번째 작은 원소

1. 피봇을 A[left]~A[right] 중에 선택
2. 피봇을 A[left]와 자리 변경
3-1. 피봇과 각 배열의 원소를 비교, 피봇보다 작은 수는 피봇의 왼편(A[left]~A[pivot-1])으로 옮긴다.
3-2. 피봇보다 큰 수는 피봇의 오른편(A[pivot+1]~A[right])으로 옮긴다.
		*피봇은 항상 A[pivot]에 위치해야한다.

S = (pivot-1)-left+1 // 작은 수 배열의 사이즈

if(k<=S) Selection(A, left, p-1, k)  // 찾는 수가 작은 수 배열에 속하여 작은 수 배열 탐색
else if(k=S+1) return A[p]           // 찾는 수가 피봇과 같으면 피봇 반환
else Selection(A, p+1, right, k-S-1) // 찾는 수가 큰 수 배열에 속하여 큰 수 배열 탐색

의사코드를 통해 다음을 확인할 수 있다.

1. **[배열과 시작/끝 범위, 찾을 목표 숫자]**의 정보를 받는다
2. 피봇을 랜덤으로 선택 및 배열의 첫 자리와 위치를 변경한다.
3. 피봇을 기준으로 왼편에 피봇보다 작은 수 / 오른편에 피봇보다 큰 수를 나열한다.
4. 작은 수 배열 크기를 구한다.
5. 찾는 목표가 작은 수 배열 크기보다 작으면 작은 수 배열에 찾는 목표가 있기에 작은 수 배열만 다시 탐색한다.
6. 피봇과 찾는 목표가 같으면 피봇을 반환한다.
7. 위 5와 6에 해당하지 않는다면 찾는 목표는 큰 수 배열에 존재하기에 큰 수 배열을 다시 탐색한다.

 

/// 정렬되어야하는 배열의 첫 값, 중앙 값, 끝 값 중에서 중간 값 구하는 함수
/// <data1 : int *left>   가장 왼쪽 배열 원소
/// <data2 : int *middle> 중앙 배열 원소
/// <data3 : int *right>  가장 오른쪽 배열 원소
/// <return : int> 주어진 세개의 원소 중에서 중간 값을 반환
int* 선택문제::middle(int *left, int *middle, int *right)
{
	// 중앙 원소가 중간 값이면 반환
	if ((*left >= *middle && *middle >= *right) || (*right >= *middle && *middle >= *left))
		return middle;
	
	// 왼쪽 원소가 중간 값이면 반환
	if ((*middle >= *left && *left >= *right) || (*right >= *left && *left >= *middle))
		return left;
	
	// 오른쪽 원소가 중간 값이면 반환
	if ((*left >= *right && *right >= *middle) || (*middle >= *right && *right >= *left))
		return right;
	
	// 예외 처리
	return left;
}

/// 두 정수를 바꾸는 함수
/// <data1 : int *a> b와 바뀔 수
/// <data2 : int *b> a와 바뀔 수
void 선택문제::swap(int *a, int *b) {
	int temp = *a;
	*a = *b;
	*b = temp;
}

/// <data1 : int A[]>     정렬해야하는 배열
/// <data2 : int left>    배열의 시작점
/// <data3 : int right>   배열의 끝점
/// <data4 : int k>       찾는 자릿 수
/// 입력 : 배열 A[left]~A[right]와 k. 단, 1 <= k <= |A|, |A|=right-left-1
/// 출력 : 정렬된 배열 A[left]~A[right]에서 k번째 작은 원소
int Selection(int[] A, int left, int right, int k)
{
	// ================================= 예외처리 ================================= //

	// 1. 찾는 자릿 수가 존재하지 않는 경우 종료
	// 2. 찾는 자릿 수가 배열의 크기를 넘는 경우 종료
	if (k < 1 || k > (right - left - 1))
	{
		printf("Wrong input error\\n");
		printf("Target number : %i \\n", k);
		printf("Minimum : %i", left);
		printf("Maximum : %i", right);
		printf("Length of Array : %i", (right - left - 1));
		return -1;
	}

	// 찾는 범위가 없고 찾는 자릿 수가 1개이면 현재 배열 유일 원소 반환
	if (left == right && k == 1) return A[left];
	
	// ================================= 퀵정렬 ================================= //

	int begin = left;
	int end = right;

	//피봇 정의 시작
	//중간 값을 가지는 pivot을 구하는 함수
	int *pivot = 선택문제::middle(&A[begin], &A[(end/2)], &A[end]); // 처음, 중간, 끝의 배열을 비교하여 피봇 생성

	// 피봇이 첫 배열이 아니라면 첫 배열로 이동시키며 첫 배열 값을 피봇과 교환한다.
	if (pivot != &A[begin])
	{
		선택문제::swap(&A[begin], pivot); // 첫 배열과 피봇의 값을 교환
	}

	pivot = &A[begin]; // 피봇을 맨 왼편 배열로 선언

	 
	// 앞에서부터 큰 수를 찾는 b와 뒤에서부터 작은 수를 찾는 e가 서로 같은 위치가 아니라면 반복
	while (true) {
		// 피봇보다 큰 값을 찾는 반복자
		// b의 원소가 피봇보다 작고 b가 e보다 작을때 계속 다음 원소를 찾는다.
		while (A[begin] <= *pivot && begin < end) 
		{
			begin++; // 큰 값이 아니면 다음 값을 봄
		}
		// 피봇보다 작은 값을 찾는 반복자
		// e의 원소가 피봇보다 크고 b가 e보다 작을때 계속 다음 원소를 찾는다.
		while (A[end] > *pivot && begin < end) 
		{
			end--; // 작거나 같은 값이 아니면 다음 값을 봄
		}
		
		// b와 e가 같으면 원소 위치를 바꾸거나 탐사를 할 이유가 없기에 반복문을 나간다.
		if(begin == end) break;

		// 위 두 조건을 만족하면 왼편에서 더 큰수가 오른편에서 더 작은 수가 발견된 것으로 둘을 바꾸어야한다.
		// 위의 두 반복문이 완료되면 e와 b는 같은 자리의 수를 가르킨다.
		선택문제::swap(&A[begin], &A[end]);
	}
	
	// 이제 피봇을 e의 자리와 변경하여 두 배열의 중앙에 위치하게 한다
	선택문제::swap(pivot, &A[end-1]);
	

	// ================================= 선택문제 ================================= //

	
	int S = (end-2) - left + 1; // 작은 수 배열의 사이즈 확인
	
	if(k<=S) Selection(A, left, (end-1), k);  // 찾는 수가 작은 수 배열에 속하여 작은 수 배열 탐색
	else if(k=S+1) return A[pivot];              // 찾는 수가 피봇과 같으면 피봇 반환
	else Selection(A, (end+1), right, k-S-1);    // 찾는 수가 큰 수 배열에 속하여 큰 수 배열 탐색
}

크기가 8인 배열 [1, 5, 3, 2, 0, 4]에서 2번째 작은 수를 찾는다는 예제를 들어보자.

1. 입력값 받음
   1. A = [1, 5, 3, 2, 0, 4]
   2. left = 0
   3. right = 5
   4. k = 2
2. 예외처리문 확인
   1. k < 1
      1. 찾는 자리가 존재하는가?
   2. k > (right - left - 1)
      1. 찾는 자리가 배열을 넘지 않는가?
3. 퀵정렬
   1. 피봇을 정하기
   2. 피봇을 기준으로 왼편에 작은 수 / 오른편에 큰 수를 집합
   3. 피봇을 두 집합 중앙으로 이동
4. 작은 수 배열의 크기 확인
5. 정답 확인
   1. 찾는 자릿 수가 작은 수 배열에 포함되어 있다면 작은 수 배열을 재귀함수로 호출
   2. 찾는 자릿 수가 현재 피봇과 동일하면 현재 피봇 반환
   3. 찾는 자릿 수가 큰 수 배열에 포함되어 있다면 큰 수 배열을 재귀함수로 호출