Selection

문제 정의 : k등을 찾아라!

- Sorting 보다 빨라야 도움이 된다. ( 퀵소트에서 중간값을 찾는 경우 등)

- 토너먼트 식으로 한다면? 

1등을 찾는데에는 n, 2등을 찾는데에는 n + logn, 3등을 찾는데에는 n + 2logn,

k등을 찾는데에는 n + klogn이 걸리게 된다.

- Selection Sort를 k번째 까지 수행한다면?

kn 시간이 걸림 -> k가 n/2이면 O(n^2)이 걸리게 된다.

- Quick Sort를 k등 근처에서 수행한다면?

최선의 경우 O(n)에 끝나지만,

최악의 경우 O(n^2)이 걸리고 평균적으로 O(n)이 된다.

-> Selection 문제를 "최악의 경우에도" n^2이 안 걸리게 풀 수 있는 알고리즘이 있을까?

-> 있지만, 슬프게도, 실용적이지는 않다.

* Approximate Median

정의 : rn등부터 (1-r)n등 사이의 원소. (단, 0 < r < 1)

- 매우 약한 정의이기는 하지만 이렇게 주어져도 문제 없다는 것이 증명되어 있음. ( = 그냥 믿으세요! )

- r = 0.3으로 고정한다.

Alg.

  1. 배열을 5개씩 분할

  2. 각 분할의 중간값을 찾는다.

  3. 중간값들 중 실제 중간값을 찾는다.

결론 : 3번에서 찾은 '실제 중간값'은 반드시 rn등과 (1-r)n등 사이에 존재한다.

* 정확성 증명

입력이 ㅇㅇㅇㅇㅇㅇㅇㅇㅇㅇㅇㅇㅇㅇㅇㅇㅇㅇㅇㅇㅇㅇㅇㅇㅇ 이라고 한다면

1번에서

ㅇㅇㅇㅇㅇ | ㅇㅇㅇㅇㅇ | ㅇㅇㅇㅇㅇ | ㅇㅇㅇㅇㅇ | ㅇㅇㅇㅇㅇ 

- 단, 실제로 나누는 것이 아니고 그렇게 생각하는 것.

2번을 이해하기 쉽게 배열을 세로로 나타내면

ㅇ | ㅇ | ㅇ | ㅇ | ㅇ | 

ㅇ | ㅇ | ㅇ | ㅇ | ㅇ | 

ㅇ | ㅇ | ㅇ | ㅇ | ㅇ | 

ㅇ | ㅇ | ㅇ | ㅇ | ㅇ | 

ㅇ | ㅇ | ㅇ | ㅇ | ㅇ | 

- 위에 있을수록 큰 값, 아래에 있을수록 작은 값.

- 3번째 줄, 즉 가운데 값이 각 분할된 배열의 중간값이다.

가운데 값을 기준으로 각 분할된 배열을 정렬한다.

(여기서는 증명 과정을 알아보기 쉽도록 정렬을 하지만, 실제 구현에서는 모든 분할 배열을 정렬할 필요없이,
 3번째 줄의 진짜 중간값만 찾으면 된다.)

ㅇ | ㅇ | ㅇ | ㅇ | ㅇ | 

ㅇ | ㅇ | ㅇ | ㅇ | ㅇ | 

ㅇ | ㅇ | ㅇ | ㅇ | ㅇ |  <- 정렬되어 있음.

ㅇ | ㅇ | ㅇ | ㅇ | ㅇ | 

ㅇ | ㅇ | ㅇ | ㅇ | ㅇ | 

1,2, 4,5번째 줄은 좌우로는 크기비교를 할수 없지만, 위의 것보다는 작고, 아래의 것보다는 크다.

3번에 의해 찾은 실제 중간값을 ☆ 이라 하자.

ㅇ | ㅇ | ㅇ | ㅇ | ㅇ | 

ㅇ | ㅇ | ㅇ | ㅇ | ㅇ | 

ㅇ | ㅇ | ☆ | ㅇ | ㅇ | 

ㅇ | ㅇ | ㅇ | ㅇ | ㅇ | 

ㅇ | ㅇ | ㅇ | ㅇ | ㅇ | 

- 위에서 빨간색으로 표시된 것들은 무조건 ☆보다 큰 값이다.

- ☆의 위에 있는 값들은 분할된 배열이 정렬되어 있기때문이고, ☆의 오른쪽에 있는 값들은 3번째줄을 기준으로 정렬했기 때문이고,

☆의 오른쪽 위에 있는 값들은 

 ☆ < (☆의 오른쪽) < (☆의 오른쪽)의 위

이기 때문이다.

- 따라서, 예제의 입력된 배열에는 ☆보다 큰 값이 최소한 8개 존재하며,

 입력된 배열이 n개 일때, ☆보다 큰 값이 최소한 (대략) 3n/10개 존재한다.

 -> 즉, ☆이 아무리 커도 상위 30%이내에는 들어갈 수 없다.

위와 같은 식으로,

ㅇ | ㅇ | ㅇ | ㅇ | ㅇ | 

ㅇ | ㅇ | ㅇ | ㅇ | ㅇ | 

ㅇ | ㅇ | ☆ | ㅇ | ㅇ | 

ㅇ | ㅇ | ㅇ | ㅇ | ㅇ | 

ㅇ | ㅇ | ㅇ | ㅇ | ㅇ | 

- 위에서 빨간색으로 표시된 것들은 무조건 ☆보다 작은 값이다.

- ☆의 아래에 있는 값들은 분할된 배열이 정렬되어 있기때문이고, ☆의 왼쪽에 있는 값들은 3번째줄을 기준으로 정렬했기 때문이고,

☆의 왼쪽 아래에 있는 값들은 

 ☆ > (☆의 왼쪽) > (☆의 왼쪽)의 아래

이기 때문이다.

- 따라서, 예제의 입력된 배열에는 ☆보다 작은 값이 최소한 8개 존재하며,

 입력된 배열이 n개 일때, ☆보다 작은 값이 최소한 (대략) 3n/10개 존재한다.

 -> 즉, ☆이 아무리 작아도 하위 30%이내에는 들어갈 수 없다.

=> 따라서 ☆이 전체 입력의 30% ~ 70% 사이에 존재한다.

=> Approximate Median이 성립함.

 * 3번에서 "실제 중간값"을 찾기 위해서 Quick sort를 호출한다.

그리고 그 Quick sort는 pivot을 찾기 위해 Approximate Median을 호출한다.

=>Quick sort ( 이하 QS )와 Approximate Median ( 이하 AM )이 상호재귀함수로서 작동한다.

- QS(n)은 AM(n)과 QS(0.7n)을 호출한다.

   -> 입력된 것을 그대로 AM으로 보내 pivot을 찾고, 그 pivot은 최악의 경우에도 70%안쪽이므로 0.7n으로 다시 QS를 호출할 수 있다.

- AM(n)은 QS(0.2n)을 호출한다.

   -> 입력을 5개씩 분할하고 각 분할된 배열의 중간값만을 QS로 보내 실제 중간값을 찾는다. 

* Selection 문제를 푸는 시간을 t(n)이라 하면

t(n) = n + t(2n/10) + t(7n/10)

t(n) <= Cn이라고 가정하면

t(n) = n + 2Cn/10 + 7Cn/10 

      = 9Cn/10 + n

      = (9C+10)*n/10 

C가 커질수록 (9C+10)/10 의 값이 작아진다.

( C가 10일때 10, 20일때 19, 30일때 28 .........)

즉 t(n) <= 10n

따라서 t(n) = O(n)