1. Selection Problem and Approximate Median quick sort에서 우리는 어떻게 가장 좋은 pivot을 얻을 수 있을까? 만약 우리가 O(N)에 best pivot을 뽑으면 최악의 경우가 O(nlogn)가 되지 않을까? Selection Problem 은 k번째 작은 것들을 찾는 것이다. 이것은 median을 찾는것과 비슷한 시간복잡도는 갖는다. Selection Problem을 O(nlog)으로 구현하는 것은 쉽다. 그냥 sorting 하면되기 때문이다. 하지만 O(nlog)은 필요가 없다. 2. Selection Approximate Median with Quick Sort pivot으로써 Approximate Median을 찾으면 quick sort를 O(nlog..