선형 시간에 중간값 구하기 (Quick-Select & Median-of-Medians)

Photo by Deniz Altindas on Unsplash

이번 포스트에서 함께 공부할 내용은 중간값(median)을 구하는 방법입니다. 중간값은 어떤 수열을 오름차순으로 정렬했을 때 가운데에 위치한 수를 의미합니다. 예를 들어, 수열이 \[ 4, 8, 3, 1, 6 \]으로 주어졌을 때, 이를 오름차순으로 정렬하면 \[ 1, 3, 4, 6, 8 \]이 되고, 여기서 중간값은 \(4\)가 되겠습니다. 만약 수열의 길이가 짝수라면 중간에 위치한 수는 두 개가 됩니다. 이 글에서는 크기가 다르다면 둘 중 크기가 더 작은 값을 중간값으로 정의하겠습니다.

 

중간값을 구하는 가장 간단한 방법은 수열을 먼저 정렬한 후에 가운데에 위치한 수를 찾는 것입니다. (비교 기반) 정렬 알고리즘은 수열의 길이 \(n\)에 대해 \( \Theta(n \log n) \)에 수행된다는 사실이 잘 알려져 있습니다. 과연 그보다 더 빠른 속도로 중간값을 찾는 방법이 존재할까요? 놀랍게도 존재합니다. 이번 시간에는 이에 대해 함께 알아보도록 하겠습니다.

\(k\)번째로 작은 숫자 찾기

풀고자 하는 문제를 약간 확장해 봅시다. 이 문제에서는 어떤 수열이 주어집니다. 이때, 수열의 모든 숫자는 서로 다르다고 가정합니다. 이 가정이 그리 나쁘지 않은 이유는 중복된 숫자가 존재하는 수열을 쉽게 중복이 존재하지 않는 것으로 바꾸는 방법이 있기 때문입니다. 자세한 내용은 이전 포스트를 참조하여 주세요.

2020/08/01 - [연습 노트] - 확률 퀵 정렬 분석 (Analysis on Randomized Quick-Sort)

확률 퀵 정렬 분석 (Analysis on Randomized Quick-Sort)

우리가 찾고자 하는 것은 이 수열에서 \(k\)번째로 작은 숫자입니다. 다시 말해, 수열을 오름차순으로 정렬한 것을 \[ a_1, a_2\, \cdots, a_n \]이라고 했을 때, \( a_k \)의 값이 무엇인지를 찾는 것이죠. 중간값은 \( \lfloor \frac{n}{2} \rfloor \)번째로 작은 숫자이므로 이 문제를 해결할 수 있으면 충분히 중간값도 찾을 수 있습니다.

 

참고로 아래에서는 올림(\( \lceil \cdot \rceil \))과 버림(\( \lfloor \cdot \rfloor \))을 제대로 처리하지 않고 분석하였습니다. 보다 엄밀한 증명을 위해서는 이를 잘 처리해 주어야 합니다만, 계산만 복잡해지고 직관적으로도 그리 어렵지 않다고 생각하여 생략하였습니다.

퀵 선택(Quick-Select) : 확률적으로 빠른 시간에 찾는 방법

첫 번째 방법은 이름에서 쉽게 유추할 수 있듯이 퀵 정렬(quick-sort)과 유사한 분할 정복(divide-and-conquer) 방법입니다. 주어진 수열에서 임의로 숫자 \(x\)를 하나 골라 축(pivot)으로 두고, 그것보다 작은 숫자들과 큰 숫자로 분류합니다. 작은 숫자들의 개수를 \( i \)라고 할 때, 만약 \( k \leq i \)라면, 분명 \(k\) 번째로 작은 숫자는 \(x\)보다 작은 숫자일 것이므로 \(x\)보다 작은 숫자들 중에서 \(k\) 번째로 작은 숫자를 찾습니다. 반대로 \( k > i \)라면, \(x\)보다 크거나 같은 숫자들 중에 존재할 것이기 때문에 그 숫자들 중에서 \( k - i \)번째로 작은 숫자를 찾습니다. 이를 수열의 길이가 \(1\)이 될 때까지 재귀적으로 반복해주면 됩니다.

 

최악의 경우에 이 알고리즘은 얼마큼의 시간을 필요로 할까요? 예를 들어, 우리는 가장 작은 숫자를 찾고 싶은데, 매 재귀 호출마다 가장 큰 숫자를 축으로 잡으면 다음 재귀 호출에서의 수열 길이는 겨우 \(1\) 밖에 줄지 않습니다. 따라서 \(n\)의 길이를 갖는 수열에서 퀵 선택이 쓰는 시간을 \( T(n) \)이라고 하였을 때, \[ T(n) = \left\{ \begin{array}{ll}  O(1), & \text{if } n \leq 1,\\ T(n - 1) + \Theta(n), & \text{otherwise} \end{array} \right. \]라는 점화식을 얻게 되고 이를 풀면 \( T(n) = O(n^2) \)이라는 멍청한 시간 복잡도를 얻게 됩니다. 수열을 정렬한 후 \(k\) 번째로 작은 숫자를 바로 얻는 알고리즘이 \( O(n \log n) \)이라는 것을 감안하면 정말로 느린 수치가 아닐 수 없습니다.

 

이는 퀵 정렬에서도 나타난 문제점이었습니다. 이를 해결하기 위해서 수열에서 축을 균일한 확률(uniformly at random)로 선택하였죠. 퀵 선택에서도 동일한 방식으로 축을 골라보도록 하겠습니다.

알고리즘 1. Randomized quick-select

---

입력: 수열 \(a_1, \cdots, a_n\), 정수 \(k\)

출력: 수열에서 \(k\)번째로 작은 값

 

1. 만약 \(n = 1\)이면, \(a_1\)을 반환한다.
2. 그렇지 않다면, 주어진 수열에서 균일한 확률(uniformly at random)로 \(x\)를 선택한다.
3. 이를 축으로 \( A_{< x} := \{ a_1^\prime, \cdots, a_i^\prime \} \)과 \( A_{\geq x} := \{ x, a_{i + 2}^\prime, \cdots, a_n^\prime \} \)으로 수열을 쪼갠다.
4. 만약 \(k \leq i\)라면 \(A_{< x}\)에서 \(k\)번째 수를 재귀적으로 찾는다. 그렇지 않다면 \( A_{\geq x} \)에서 \(k - i\)번째 수를 재귀적으로 찾는다.

알고리즘이 올바른 결과를 출력한다는 사실은 그다지 어렵지 않으므로 생략하도록 하겠습니다. 이 알고리즘은 \(x\)를 어떻게 선택하는지에 따라서 수행 시간이 달라지는 확률 알고리즘(randomized algorithm)입니다. 그러므로 이 알고리즘의 수행 시간의 기댓값을 대신 구하도록 하겠습니다.

그림 1. \(x = b_{j + 1}\)으로 선택되었을 때, \( A_{< x} \)와 \( A_{\geq x} \). 왼쪽 빨간색은 \( A_{< x} \)로 그 개수가 \(j\)개이며, 오른쪽 파란색은 \( A_{\geq x} \)로 그 개수가 \(n - j\)가 된다.

수열의 길이가 \(n\)일 때 알고리즘의 수행 시간의 기댓값을 \(T(n)\)이라고 하겠습니다. 수열이 \( a_1, \cdots, a_n \)으로 주어졌을 때, 이를 오름차순으로 정렬한 것을 \(b_1, \cdots, b_n\)이라고 하겠습니다. 다시 말해, \( \{b_1, \cdots, b_n\} = \{ a_1, \cdots, a_n \}\)이며 \( b_1 < \cdots < b_n \)입니다. 만약 알고리즘이 단계 2에서 \(x = b_{j + 1}\)을 골랐다고 하겠습니다. 그러면 \( |A_{< x}| = j \)이고 \( |A_{\geq x}| = n - j \)가 됩니다.(그림 1) 따라서 다음 재귀 호출에서 살아 남는 수열은 아무리 길어도 \( j \)와 \( n - j \) 중 최댓값을 넘지 못합니다.

그림 2. 못해도 수열의 길이를 \(\frac{3n}{4}\)로 줄이는 경우의 수.

따라서 \(j\)가 만약 \( \frac{n}{4} \leq j \leq \frac{3n}{4} \)라면 수열의 길이는 아무리 길어도 \( \frac{3n}{4} \)을 넘지 못하게 됩니다. 균등한 확률로 \(j\)를 골랐으므로 \(j\)가 해당 조건을 만족할 확률은 \( \frac{1}{2} \)입니다.(그림 2) 반대의 경우에는 수열의 길이가 \(n\)을 넘지는 않는다는 자명한 상한이 존재합니다. 이를 조합하면 다음과 같은 점화식을 세울 수 있게 됩니다.

\[ T(n) \leq \left\{ \begin{array}{ll} c, & \text{if } n = 1, \\ \frac{1}{2} T (\frac{3n}{4}) + \frac{1}{2} T(n) + d \cdot n, & \text{otherwise. } \end{array} \right. \]

이때, 첫 번째 줄의 \(c\)는 단계 1에서 소요되는 시간입니다. 두 번째 줄의 \(d \cdot n\)은 단계 3에서 \( A_{< x} \)와 \( A_{\geq x} \)로 나누는데 소요되는 시간으로, 이 작업도 선형 시간에 할 수 있으므로 \(d\)도 상수입니다. 이 식을 풀면 \( a \geq \max( c, 8d ) \)를 만족하는 어떤 상수 \(a\)에 대해 \( T(n) \leq a \cdot n \)임을 보일 수 있고 따라서 \( T(n) = O(n) \)이 됩니다.

중간값의 중간값(Median-of-Medians) : 좋은 축을 찾는 방법

퀵 선택에 확률을 적용하면 선형 시간에 \(k\)번째로 작은 수를 찾을 것으로 기대할 수 있었습니다. 하지만 이 알고리즘은 여전히 매 재귀 호출마다 축을 멍청하게 골라서 제곱 시간에 동작할 여지를 남겨두고 있습니다. 그럼에도 알고리즘의 수행 시간의 기댓값이 여전히 선형일 수 있는 이유는 높은 확률(\(\frac{1}{2}\))로 고려해야 하는 수열의 길이를 크게 줄이기 때문입니다.(\( n \rightarrow \frac{3n}{4} \))

 

따라서 항상 수열의 길이를 유의미한 수치로 줄일 수 있다면 알고리즘은 어떤 입력에 대해서도 선형 시간이 걸리게 될 것입니다. 그러한 축을 찾는 방법이 바로 중간값의 중간값(median-of-medians) 기법입니다. 알고리즘 1에서 축을 확률적으로 선택하는 부분을 이 기법으로 갈아 끼우면 다음과 같은 결정론적 알고리즘(deterministic algorithm)이 됩니다.

알고리즘 2. Deterministic quick-select with median-of-medians

---

입력: 수열 \(a_1, \cdots, a_n\), 정수 \(k\)

출력: 수열에서 \(k\)번째로 작은 값

 

1. 만약 \(n \leq 5\)라면, 직접 \(k\)번째로 작은 수를 찾고 이를 반환한다.
2. 그렇지 않다면 주어진 수열을 다섯 개씩 분할한다. 즉, \[ A_1 := \{ a_1, \cdots, a_5 \}, \quad A_2 := \{ a_6, \cdots, a_{10} \}, \quad \cdots, \quad A_{\lceil n/5 \rceil} := \{ a_{5 \lfloor n/5 \rfloor + 1}, \cdots, a_n\} \]이 되도록 분할한다.
3. \(A_1, \cdots, A_{\lceil n/5 \rceil}\)에서 각각 재귀적으로 중간값을 찾는다. 이렇게 찾은 중간값을 \( b_1, \cdots, b_{\lceil n/5 \rceil} \)라고 하자.
4. \( b_1, \cdots, b_{\lceil n/5 \rceil} \)의 중간값을 재귀적으로 찾는다. 이를 \(x\)라고 부르자.
5. 원래 수열 \(a_1, \cdots, a_n\)을 \(x\)보다 작은 값 \(A_{< x} := \{ a_1^\prime, \cdots, a_i^\prime \} \)과 \(x\)보다 크거나 같은 값 \( A_{\geq x} := \{x, a_{i + 2}^\prime, \cdots, a_n^\prime\} \)으로 쪼갠다.
6. 만약 \(k \leq i\)라면 \(A_{< x}\)에서 \(k\)번째 수를 재귀적으로 찾는다. 그렇지 않다면 \( A_{\geq x} \)에서 \(k - i\)번째 수를 재귀적으로 찾는다.

단계 5와 6은 알고리즘 1의 단계 3과 4에 대응됩니다. 따라서 이 알고리즘이 항상 올바른 출력을 준다는 것은 쉽게 보일 수 있습니다. 확률에 의존하던 알고리즘 1의 단계 2가 알고리즘 2에서는 단계 2-4로 치환되었으므로, 더 이상 알고리즘 2는 확률 알고리즘이 아닙니다.

 

참고로 이 기법의 이름이 중간값의 중간값인 이유는 \(x\)가 \(A_1, \cdots, A_{\lceil n/5 \rceil}\)의 중간값들인 \(b_1, \cdots, b_{\lceil n/5 \rceil}\)의 중간값이기 때문입니다. 일반적으로 \(x\)가 본래 수열의 중간값이 되는 것은 아닙니다. 예를 들어, \[ 1, 2, 10, 11, 12, 3, 4, 20, 21, 22, 5, 6, 30, 31, 32 \]에서 \[ \{1, 2, 10, 11, 12\}, \{3, 4, 20, 21, 22\}, \{5, 6, 30, 31, 32\} \] 각각의 중간값은 \( 10, 20, 30 \)이 되어 중간값의 중간값은 \(20\)이 되나, 원래 수열에서의 중간값은 \(11\)입니다.

 

하지만 우리는 \(x\)가 본래 수열의 꽤 중앙에 있는 값이라는 것을 보일 수 있습니다. 좀더 쉽게 표현하기 위해서 일반성을 잃지 않고 수열의 인덱스값을 다음과 같이 수정하겠습니다. 이는 알고리즘 2의 인덱스와는 다르므로 헷갈리지 마시기 바랍니다. 먼저 \(b_1, \cdots, b_{\lceil n/5 \rceil}\)는 \[ b_1 < \cdots < b_{\lceil n/5 \rceil}  \]을 만족한다고 하겠습니다. 또 \(b_j\)는 \(A_j\)의 중간값이라고 하겠습니다. 그러면 \(x = b_{\lfloor n/10 \rfloor} \)가 되겠죠.

그림 3. 수열에서 \(x\)보다 큰 수의 개수. \( x = b_4 \)일 때, 파란색으로 표현한 수는 반드시 \(x\)보다 크거나 같으며 그 개수는 \( \frac{3n}{10} \) 정도 된다. 빨간색은 \(x\)보다 작을 수도 있는 수를 나타낸 것으로 그 개수는 \( \frac{7n}{10} \)을 넘지 않는다.

자, 이제 \(x\)보다 수열에서 크거나 같은 값이 최소한 몇 개 있는지 찾아 보겠습니다. \( x = b_{\lfloor n/10 \rfloor} < \cdots < b_{\lceil n/5 \rceil} \)이므로 \(A_{\lfloor n/10 \rfloor}, \cdots, A_{\lceil n/5 \rceil}\)의 중간값들은 모두 \( x \)보다 크거나 같습니다. 우리는 단계 2에서 수열을 다섯 개씩 분할하였으므로, 분명 각각의 부분 수열에서 최소 세 개씩은 \(x\)보다 크거나 같다는 것을 알 수 있습니다. 부분 수열의 개수가 \( \frac{n}{10} \) 개 정도 되므로, 원래 수열에서 \(x\)보다 크거나 같은 수의 개수는 최소 \( \frac{3n}{10} \) 정도는 됩니다. 따라서, \(x\)보다 작은 수의 개수는 아무리 많아도 \( \frac{7n}{10} \)을 넘지 않는 것이죠.(그림 3)

 

이 논의를 반대로 적용하면 \(x\)보다 큰 수의 개수도 \( \frac{7n}{10} \)을 넘지 않는다는 것을 쉽게 보일 수 있습니다. 따라서 단계 5의 \( A_{< x} \)와 \( A_{\geq x} \)의 크기가 모두 \( \frac{7n}{10} \)을 넘지 않게 됩니다. 따라서 우리는 수열의 길이가 \(n\)일 때의 알고리즘 2의 수행 시간 \(T(n)\)에 대해 다음과 같은 점화식을 세울 수 있습니다.

\[ T(n) \leq \left\{ \begin{array}{ll} c, & \text{if } n \leq 5, \\ T(\frac{n}{5}) + T (\frac{7n}{10}) + d \cdot n, & \text{otherwise. } \end{array} \right. \]

이때, 첫 번째 줄은 상수 \(c\)는 알고리즘 2의 단계 1에서 걸리는 시간의 상한을 나타냅니다. 또, 두 번째 줄에서 \( T(\frac{n}{5}) \)는 단계 4에서 \( b_1, \cdots, b_{\lceil n/5 \rceil} \)에서 중간값을 재귀적으로 찾는 데 걸리는 시간이며, \(d \cdot n\)은 단계 2에서 수열을 다섯 개씩 쪼개고 단계 3에서 각각의 부분 수열에서 중간값을 구하는 데 걸리는 시간의 상한을 나타냅니다. 위에서 다음 재귀 호출에서의 배열 길이가 \( \frac{7n}{10} \)을 넘지 않음을 논의하였으므로 \(T(\frac{7n}{10})\)이 들어가게 됩니다. 이 식을 풀면, \( a \geq \max(c, 10d) \)인 상수 \(a\)에 대해 \( T(n) \leq a \cdot n \)임을 보일 수 있고, 따라서 \( T(n) = O(n) \)이 됩니다.

마치며

이것으로 선형 시간에 중간값을 구할 수 있는 방법인 퀵 선택에 대해서 설명을 마칩니다. 퀵 선택은 축을 아무렇게나 고르면 최악의 경우 \( O(n^2) \)의 시간을 소모하게 됩니다. 하지만 균등한 확률로 수열에서 수를 하나 고르면 \( O(n) \)의 수행 시간을 기대할 수 있게 됩니다. 나아가, 수열을 잘게 쪼갠 후, 각각 중간값을 구한 다음, 그것들의 중간값을 축으로 고른다면 다음 재귀 호출에서의 수열의 크기를 유의미한 크기로 줄일 수 있게 되어, 어떤 입력이 들어오더라도 선형 시간에 퀵 선택을 수행할 수 있게 됩니다.

 

중간값의 중간값 기법은 퀵 정렬에서도 활용될 수 있습니다. 그러면 어떤 입력이 들어와도 항상 \( O(n \log n) \)의 수행 시간을 보장할 수 있게 되며, 이로써 최악의 경우에도 다른 빠른 정렬인 병합 정렬(merge-sort)나 힙 정렬(heap-sort)과도 동일한 시간 복잡도를 갖게 되는 것이죠. 물론 제 생각에, 현실적으로는 수열에서 균등한 확률로 뽑는 알고리즘이 훨씬 빠르지 않을까 생각합니다만, 여전히 이론적으로 흥미로운 결과임에는 틀림이 없습니다.

 

궁금하신 점이 있으시거나, 잘못된 점을 찾으셨다면 알려주시기 바랍니다. 감사합니다. :)

참조

[1] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to algorithms. MIT press, 2009. (a.k.a. CLRS)