선형 시간에 중간값 구하기 (Quick-Select & Median-of-Medians)
이번 포스트에서 함께 공부할 내용은 중간값(median)을 구하는 방법입니다. 중간값은 어떤 수열을 오름차순으로 정렬했을 때 가운데에 위치한 수를 의미합니다. 예를 들어, 수열이 \[ 4, 8, 3, 1, 6 \]으로 주어졌을 때, 이를 오름차순으로 정렬하면 \[ 1, 3, 4, 6, 8 \]이 되고, 여기서 중간값은 \(4\)가 되겠습니다. 만약 수열의 길이가 짝수라면 중간에 위치한 수는 두 개가 됩니다. 이 글에서는 크기가 다르다면 둘 중 크기가 더 작은 값을 중간값으로 정의하겠습니다. 중간값을 구하는 가장 간단한 방법은 수열을 먼저 정렬한 후에 가운데에 위치한 수를 찾는 것입니다. (비교 기반) 정렬 알고리즘은 수열의 길이 \(n\)에 대해 \( \Theta(n \log n) \)에 수행된다는 사실..
