[알고리즘] Selection 알고리즘

 

 

 

 

 

 

🧐 Selection 알고리즘

크기가 $n$ 인 배열 $A$ 가 주어졌을 때, $A$ 에서 $k$ 번째로 작은 요소를 찾는 알고리즘에 대해 알아보도록 하겠습니다.

 

가장 간단한 방법으로는 $A$ 를 정렬하여 $k$ 번째 수를 가지고 오는 방법이 있습니다.

 

배열을 정렬하는 알고리즘들 중에서 worst-case가 $O(n \; logn)$ 인 알고리즘(merge sort, heap sort, 등등)을 사용한다면, 이후 $k$ 번째 요소에 접근하는 것은 $O(1)$ 의 시간이 소요되므로 총 시간 복잡도는 $O(n \; log n)$ 입니다.

 

 

두번째 방법은 Devide and Conquer 알고리즘 중 하나인 Quick Select 알고리즘을 사용하는 것입니다.

 

 

 

 

 

 

 

 

 

 

 

🧐 Quick Select

Quick Select는 Quick Sort와 유사한 방법으로, 다음과 같은 순서로 이루어집니다.

 

1. 배열 $A$ 의 요소들 중 아무거나 하나를 pivot으로 골라줍니다.

 

2. $A$ 를 $A_1$ (A의 원소들 중 pivot보다 작은 요소들로만 이루어진 배열)과

$A_2$ ($A$ 의 원소들 중 pivot보다 큰 요소들로만 이루어진 배열)로 Partitioning 합니다.

 

 

3. Partitioning 이후에는 다음 3가지 상황이 발생합니다.

Case 1 - $k$ 가 $A_1$ 배열의 길이 이하인(작거나 같은) 경우
👉 이 경우에는 $A_1$ 에서 $k$ 번째로 작은 요소를 찾는 subproblem의 답이 정답이 됩니다.

Case 2 - $k$ 가 $A_1$ 배열의 길이 + 1인 경우
👉 pivot 값이 $k$ 번째로 작은 값입니다.

Case 3 - $k$ 가 $A_1$ 배열의 길이 + 1보다 큰 경우
👉  $A_2$ 에서 $(k - (|A_1| + 1))$ 번째로 작은 요소를 찾는 subproblem의 답이 정답이 됩니다.


* 더해지는 1의 값은 빠지는 pivot의 개수를 포함시켜 주는 것입니다. *

 

 

 

 

시간 복잡도

$T(n)$ 을 size가 $n$ 인 array에서 quickselect를 수행하는데 걸리는 시간이라 하겠습니다.

 

$$T(n) = T(n') + O(n)$$

 

여기서 $n'$ 은 Case에 따른 $A_1$ 혹은 $A_2$ 배열의 크기가 됩니다.

 

 

 

 

 

 

최악의 경우

$A_1$ 의 크기가 언제나 0이며, $k$ 가 1보다 큰 경우이며, 이 경우에는 $n' = n - 1$ 입니다.

 

이 경우 시간 복잡도는 다음과 같이 구해집니다.

$$T(n)$$

$$= T(n-1) + O(n)$$

$$= T(n-2) + O(n) + O(n)$$

$$= T(n-3) + O(n) + O(n) + O(n)$$

$$...$$

$$= T(1) + O(n) + O(n) + ... + O(n)$$

$$= O(n^{2})$$

 

즉 최악의 경우에는 배열을 정렬하여 답을 구하는 것보다 오랜 시간이 걸리게 됩니다.

 

 

 

 

 

 

 

 

 

🧐 좋은 피벗을 고르기

위에서 살펴본 최악의 상황을 피하기 위해, 다음과 같은 규칙을 통해 pivot을 고르도록 하겠습니다.

 

1. 배열 $A$ 의 요소들 중 하나를 무작위로 골라서 pivot으로 둡니다. 

(무작위가 의미하는 것은 각 요소들이 선택될 확률이 모두 동일하다는 의미입니다.)

 

2. 해당 pivot을 통해 quickSelect를 진행합니다.

 

Case 1 : 이때 Partitioning 이후 $A_1$ 혹은 $A_2$ 의 크기가 $\frac{3n}{4}$ 을 넘으면, 새로운 pivot을 다시 무작위로 정합니다.

 

Case 2 : 만약 그렇지 않을 경우에는 그대로 quickSelect를 진행합니다.

 

 

위 방법에서 Case 2에 속하는 pivot을 Good Pivot이라 정의하도록 하겠습니다.

 

크기가 $n$ 인 배열 $A$ 에는 Good Pivot의 수가 $\frac{n}{2}$ 개 존재합니다.

(A에서 $\frac{n}{4}$ ~ $\frac{3n}{4}$ 번째로 작은 모든 요소들이 Good Pivot이기 때문입니다.)

 

따라서 $A$ 에서 Good Pivot을 고를 확률은 $\frac{1}{2}$ 입니다.

 

즉 평균적으로 2번의 시도만에 Good Pivot을 고를 수 있습니다.

 

 

 

 

 

 

시간복잡도

$T(n)$ 을 크기가 $n$ 인 배열에서 Good Pivot을 통해 quickselect를 진행하는데 걸리는 평균(expected) 시간이라 하겠습니다.

 

Good Pivot을 고를 때까지 걸리는 시간 : $O(n)$

한번 pivot을 골라 partitioning 하는데 걸리는 시간 : $O(n)$ 

Good Pivot을 고른 후 subproblem의 크기 : 최대 $\frac{3n}{4}$

 

 

따라서 평균 시간은 다음과 같습니다.

$$T(n) = T(\frac{3n}{4}) + O(n)$$

 

 

이는 Master Theorem에서 $a= 1$,  $b = \frac{4}{3}$,  $d = 1$ 인 경우에 해당합니다.

 

$log_{\frac{4}{3}} \; 1 < 1$ 이므로, 시간 복잡도는 $O(n)$ 입니다.

 

 

 

 

 

 

 

 

 

 

 

🧐  quickselect using median of medians

앞서 살펴본 방법도 결국 최악의 경우에는 시간 복잡도가 $O(n \; log \; n)$ 입니다.

 

이번에 살펴볼 quickselect using median of medians를 사용하면, 최악의 경우에도 시간 복잡도 $O(n)$ 을 보장받을 수 있습니다.

 

다음과 같은 과정으로 이루어집니다.

 

 

1. 배열 $A$ 의 크기가 25 이하이면 $A$ 를 정렬하여 문제를 해결합니다.

(이때 반드시 25여야 할 필요는 없으며, 다른 수를 지정하여도 됩니다.)

 

 

2. $A$ 의 크기가 25를 초과하는 경우, $A$ 를 크기가 5인 $\frac{n}{5}$ 개의 Subproblem으로 나눕니다.

(마찬가지로 Subproblem의 크기는 반드시 5일 필요는 없습니다. 이후 5가 아닌 경우도 살펴보도록 하겠습니다.)

 

 

3. 2에서 나눈 subArray의 median(중앙값)을 찾은 후, 이들을 배열 $M$ 에 저장합니다.

( median을 찾는 과정에서는 어떠한 알고리즘(예를들어 bubble sort 등)을 사용하여도 무방합니다. 이는 subArray의 크기가 5로 고정되어 있으므로, $O(1)$ 시간이 소요되기 때문입니다.)

 

 

4. 배열 $M$ 의 meidan을 quickselect using median of medians( 1, 2, 3 의 과정)을 사용하여 구한 뒤, 이를 pivot으로 둡니다.

(이곳에서  quickselect using median of medians 에 대한 재귀가 발생합니다.)

 

 

5. 4에서 구한 pivot을 가지고 앞선 quick select와 마찬가지로 partitioning을 한 뒤 $A_1$ 혹은 $A_2$ 에 대하여 quickselect using median of medians를 재귀적으로 호출하여 답을 도출합니다.

 

 

 

 

 

 

 

 

수도코드 👀

 

 

 

 

 

 

 

 

시간복잡도 👀

median of medians로 진행하는 quick select의 시간 복잡도를 구하기 위해, median of medians가 얼마나 좋은 pivot인가를 알아보도록 하겠습니다.

 

 

 

노란색 부분은 왼쪽에서 오른쪽으로, 배열은 위에서 아래쪽으로 정렬되어 있다고 가정

 

 

위 상황에서 pivot, 즉 median of medians는 파란색 부분입니다.

 

 

 

 

 

위 사진에서 빨간 박스 안에 해당하는 요소들은 median of medians보다 무조건 작거나 같습니다.

 

 

즉 median of medians는 적어도 $\frac{3n}{10} (\frac{3n}{5} \times \frac{1}{2})$ 개의 요소 보다는 무조건 크거나 같습니다.

$\frac{3}{5}$ 가 의미하는 것은 5개의 subarray 중 median의 위치인 3을 의미하며, $\frac{1}{2}$ 는 전체 개수들 중 절반을 의미합니다.

 

 

 

 

 

 

 

마찬가지로 위 사진에서 빨간 박스 안에 해당하는 요소들은 median of medians보다 무조건 크거나 같습니다.

 

따라서 median of medians는 적어도 $\frac{3n}{10} (\frac{3n}{5} \times \frac{1}{2})$ 개의 요소 보다는 무조건 작거나 같습니다.

 

 

따라서 median of medians를 선택한 경우, 이를 통해 partitioning되는 subproblem의 크기는 최대 $\frac{7n}{10}$ 이 됩니다.

 

 

 

 

이제 시간 복잡도를 구해보도록 하겠습니다.

 

$T(n)$ 을크기가 n인 배열에서 quickselect with median of medians 를 하는데 걸리는 최악의 경우에 대한 시간이라 하겠습니다.

 

 

 

 

이를 recursion tree로 나타내면 다음과 같습니다.