선택 알고리즘

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 문제 정의
3. 알고리즘
4. 하한
5. 언어 지원
6. 역사
참조

1. 개요

선택 알고리즘은 주어진 값 집합에서 k번째로 작은 값을 찾거나, k개의 가장 작은 값들을 찾는 문제에 대한 알고리즘이다. 정렬, 피벗, 팩토리, 병렬, 부분 선형 자료 구조 기반의 다양한 알고리즘이 존재하며, 퀵셀렉트, 중앙값의 중앙값, Floyd-Rivest 알고리즘 등이 대표적이다. 선택 알고리즘의 실행 시간 하한은 연구되었으며, 언어별로 다양한 지원을 제공한다. 퀵셀렉트는 토니 호어에 의해 처음 제시되었고, 중앙값의 중앙값 방법은 최초의 선형 시간 결정적 선택 알고리즘으로 알려져 있다.

더 읽어볼만한 페이지

선택 알고리즘 - 퀵셀렉트
퀵셀렉트 알고리즘은 퀵 정렬과 유사한 분할 정복 알고리즘으로, 전체 리스트 정렬 대신 k번째로 작은 요소를 찾으며, 피벗을 기준으로 분할 후 재귀적으로 수행하여 평균적으로 선형 시간 복잡도를 가지지만, 피벗 선택에 따라 최악의 경우 이차 시간 복잡도를 가질 수 있어 다양한 변형과 피벗 선택 전략이 존재한다.

선택 알고리즘
개요
종류	알고리즘
분야	컴퓨터 과학
자료 구조	배열, 연결 리스트, 힙, 순서 통계 트리
알고리즘
무작위화 선택	평균 시간 복잡도 O(n)
중앙값의 중앙값	최악의 경우 시간 복잡도 O(n)
introselect	평균 시간 복잡도 O(n), 최악의 경우 시간 복잡도 O(n log n)
quickselect	평균 시간 복잡도 O(n), 최악의 경우 시간 복잡도 O(n^2)
Floyd-Rivest 알고리즘	평균 비교 횟수 n + min(k, n-k) + O(sqrt(n))
관련 주제
관련 알고리즘	정렬 알고리즘

2. 문제 정의

선택 알고리즘은 값들의 집합과 숫자 $k$ 가 주어졌을 때, $k$ 번째로 작은 값을 찾거나 $k$ 개의 가장 작은 값들의 집합을 찾는 문제이다. 이 문제를 해결하기 위해서는 값들을 정렬할 수 있어야 한다. 값들은 정수, 부동 소수점 숫자 또는 숫자 키를 가진 객체 등이 될 수 있다.

값들이 모두 다르다고 가정하거나, 같은 값에 대해서는 일관된 방법으로 순서를 매길 수 있다. 가장 작은 값은 $k=1$ 일 때, 가장 큰 값은 $n$ 개의 값들 중에서 $k=n$ 일 때 찾을 수 있다. 홀수 $n$ 에 대해 중앙값은 $k=(n+1)/2$ 일 때 찾을 수 있으며, 짝수 $n$ 에 대해서는 중앙값에 두 가지 선택이 있는데, $k=n/2$ (아래 중앙값) 또는 $k=n/2+1$ (위 중앙값)이다.

최솟값이나 최댓값을 찾는 알고리즘은 간단하게 구현할 수 있다. 예를 들어, 최솟값을 찾으려면 리스트를 순서대로 살펴보면서 현재까지 찾은 최솟값보다 작은 값이 나오면 그 값을 최솟값으로 업데이트하는 방식을 사용한다.

3. 알고리즘

Selection algorithm^영어은 값들의 모음에서 *k*번째로 작은 값을 찾는 문제에 대한 알고리즘이다. 입력값으로는 값들의 모음과 숫자 *k*를 받는다. 이 알고리즘은 *k*번째로 작은 값을 출력하거나, 문제의 변형에 따라 *k*개의 가장 작은 값들의 모음을 출력한다. 값들은 정수, 부동 소수점 숫자 등 숫자 키를 가진 객체일 수 있지만, 이미 정렬되어 있다고 가정하지는 않는다.

최댓값/최솟값 알고리즘을 응용하여 *k*번째로 작은 값을 찾는 알고리즘을 만들 수 있다. 이 알고리즘은 O(*kn*) 시간이 걸리며, *k*가 작을수록 효율적이다. 이 방법은 가장 적합한 값을 찾아 리스트의 맨 앞으로 이동시키고, *k*번째에 도달할 때까지 반복한다. 이는 불완전한 선택 정렬과 유사하다. 아래는 *k*번째로 작은 값을 찾는 알고리즘의 의사 코드이다.

'''function''' select(a[1..n], k)

'''for''' i '''from''' 1 '''to''' k

minIndex = i

minValue = a[i]

'''for''' j '''from''' i+1 '''to''' n

'''if''' a[j] < minValue

minIndex = j

minValue = a[j]

swap a[i] and a[minIndex]

'''return''' a[k]

이 방식은 *j*번째로 작은 값을 알고 있을 때, *k*번째로 작은 값을 구하는 데 O(*j* + (*k*-*j*)²) 시간이 걸린다는 장점이 있다. 또한, 선형 리스트 자료 구조를 사용할 수 있다는 장점이 있다.

최악의 경우에도 선형 시간 안에 최소값과 최대값을 구하는 알고리즘은 비교적 간단하다. 두 변수를 사용하여 리스트를 순차적으로 보면서 최댓값/최솟값을 갱신하는 방식으로 구현할 수 있다.

'''function''' minimum(a[1..n])

minIndex := 1

minValue := a[1]

'''for''' i '''from''' 2 '''to''' n

'''if''' a[i] < minValue

minIndex := i

minValue := a[i]

'''return''' minValue

'''function''' maximum(a[1..n])

maxIndex := 1

maxValue := a[1]

'''for''' i '''from''' 2 '''to''' n

'''if''' a[i] > maxValue

maxIndex := i

maxValue := a[i]

'''return''' maxValue

최대값과 최소값을 동시에 구할 때는 쌍 단위 비교나 분할 정복 알고리즘을 통해 성능을 개선할 수 있다.

3. 1. 정렬 기반 알고리즘

정렬 알고리즘을 사용하여 먼저 값들을 정렬한 후, 정렬된 배열에서 *k*번째 요소를 선택하는 방법이 있다. 이 방법의 시간 복잡도는 정렬 알고리즘에 따라 달라지는데, 비교 정렬을 사용하면

\Theta(n\log n)

시간이 걸린다.^[1]

선택 정렬처럼 한 번에 항목을 하나씩 생성하는 정렬 알고리즘을 사용하면, *k*번째 요소가 발견되는 즉시 정렬을 멈출 수 있다. 힙 정렬에 이러한 최적화를 적용하면 heapselect 알고리즘이 만들어지며, 이 알고리즘은

O(n+k\log n)

시간 안에 *k*번째로 작은 값을 선택할 수 있다.^[1]

한국에서는 퀵 정렬, 병합 정렬 등 다양한 정렬 알고리즘이 널리 사용되며, 이러한 정렬 알고리즘을 선택 알고리즘의 기반으로 활용할 수 있다.

3. 2. 피벗 기반 알고리즘

선택 알고리즘은 입력에서 "피벗" 요소를 선택하고, 이를 기준으로 나머지 값들을 피벗보다 작은 집합(

L

)과 큰 집합(

R

)으로 나눈다. 이후

k

번째로 작은 값이 어느 집합에 속하는지 판별하여 해당 집합에 대해 재귀적으로 알고리즘을 적용한다.^[1]

만약 $k \le |L|$ 이면, $k$ 번째로 작은 값은 $L$ 에 있으므로 $L$ 에 대해 재귀적으로 알고리즘을 적용한다.
만약 $k = |L| + 1$ 이면, $k$ 번째로 작은 값은 피벗 자신이므로 피벗을 반환한다.
만약 $k > |L| + 1$ 이면, $k$ 번째로 작은 값은 $R$ 에 있으며, $R$ 에서 $k - |L| - 1$ 번째 요소를 찾기 위해 재귀적으로 알고리즘을 적용한다.

피벗을 선택하고 입력을

L

과

R

로 분할하는 데에는

O(n)

시간이 걸린다. 피벗 선택 방법에 따라 성능이 달라지는데, 잘못된 피벗 선택은 최악의 경우

O(n^2)

시간을 초래할 수 있다. 피벗이 입력의 중앙값과 정확히 일치하면 각 재귀 호출은 이전 호출보다 최대 절반의 값을 가지게 되어 총 시간은 기하 급수로 합산되어

O(n)

이 된다. 그러나 중앙값을 찾는 것은 전체 입력에 대한 별도의 선택 문제이므로, 재귀 호출을 통해 중앙값을 찾으려고 하면 무한 재귀에 빠질 수 있다.

3. 2. 1. 퀵셀렉트 (Quicksort)

퀵셀렉트는 입력 값에서 피벗을 균일하게 무작위로 선택하는 알고리즘이다.^[1] 가지치기 탐색 알고리즘으로 설명될 수 있으며, 퀵 정렬과 동일한 피벗 전략을 사용하지만, 퀵 정렬과 달리 재귀 호출을 두 하위 집합 중 하나에만 수행한다.

퀵셀렉트의 예상 시간 복잡도는

O(n)

이다. 임의의 상수

C

에 대해, 비교 횟수가

Cn

을 초과할 확률은

C

에서 지수적으로 매우 작다.

퀵셀렉트 알고리즘은 퀵 정렬과 유사하게 피벗 값의 선택에 따라 성능이 달라진다. 좋지 않은 피벗 값이 지속적으로 선택되면 성능이 저하될 수 있다.

3. 2. 2. 중앙값의 중앙값 (Median of medians)

중앙값의 중앙값 방법에 대한 피벗 선택 시각화. 각 5개 요소 집합은 그림에서 열로 표시되며 위에서 아래로 오름차순 정렬. 중간값의 중앙값(중간 행의 녹색 및 보라색 점)은 왼쪽에서 오른쪽으로 오름차순 정렬. 중앙값의 중앙값을 피벗으로 선택하면, 상단 왼쪽 사분면의 $3n/10$ 개 요소는 피벗보다 작고, 하단 오른쪽 사분면의 $3n/10$ 개 요소는 피벗보다 큼. 이는 피벗팅으로 많은 요소가 제거됨을 보여줌.

'''중앙값의 중앙값'''(Median of medians)은 입력을 5개 요소 집합으로 분할하고, 각 집합의 중앙값을 상수 시간에 찾는다. 그 후 이

n/5

개 중앙값들의 중앙값을 찾기 위해 재귀적으로 자신을 호출한다. 이렇게 찾은 중앙값의 중앙값을 피벗으로 사용하면

\max(|L|,|R|)\le 7n/10

인 분할이 생성된다.^[1] 즉,

n

개 요소 문제는

n/5

개 요소(피벗 찾기)와 최대

7n/10

개 요소(피벗 사용 후)에 대한 두 개의 재귀 문제로 축소된다. 두 재귀 하위 문제의 총 크기는 최대

9n/10

이며, 총 시간은 기하 급수로 분석할 수 있다.

퀵셀렉트와 달리, 이 알고리즘은 결정적이다. 최초의 선형 시간 결정적 선택 알고리즘이었으며, 두 개의 동일한 하위 문제로 나누지 않는 분할 정복 알고리즘의 예로 학부 알고리즘 수업에서 가르치기도 한다. 그러나 시간 경계의 높은 상수 요소로 인해 실제로는 퀵셀렉트보다 느리며, 중간 크기 입력에 대해서는 정렬보다도 느리다.

최악의 경우에도 시간을 보장하기 위해 Introselect와 같은 하이브리드 알고리즘에서 중앙값의 중앙값 알고리즘으로 전환(fallback)하여 퀵셀렉트의 실질적인 성능을 달성할 수 있다.

3. 2. 3. Floyd-Rivest 알고리즘

퀵셀렉트의 변형으로, 데이터 값의 하위 집합을 무작위로 샘플링하여 피벗을 선택한다. 샘플의 위치를 기반으로 두 개의 피벗을 선택하여, k번째 값이 두 피벗 사이에 있을 확률을 높인다. 이 방법은 예상 비교 횟수를

n+\min(k,n-k)+o(n)

으로 달성할 수 있다. Floyd와 Rivest는 원래 연구에서

o(n)

항을 재귀적 샘플링 방식을 통해

O(\sqrt n)

만큼 작게 만들 수 있다고 주장했지만, 그들의 분석의 정확성은 의문시되었다. 대신, 보다 엄격한 분석을 통해 그들의 알고리즘의 한 버전이 이 항에 대해

O(\sqrt{n\log n})

을 달성한다는 것이 밝혀졌다.

퀵셀렉트와 Floyd-Rivest 알고리즘의 일반적인 분석에서는 진정한 난수 생성기의 사용을 가정하지만, 로그적으로 많은 진정한 난수 비트로 시드된 의사 난수 생성기를 사용하는 Floyd-Rivest 알고리즘의 버전은 고확률로 선형 시간에 실행되는 것으로 증명되었다.

3. 2. 4. Introselect

Introselect는 퀵셀렉트와 중앙값의 중앙값을 결합한 하이브리드 알고리즘이다. 퀵셀렉트의 빠른 평균 성능과 중앙값의 중앙값의 최악의 경우 O(n) 시간 복잡도 보장을 모두 달성한다.

Introselect는 퀵 정렬과 유사하게, 리스트를 특정 값(피벗)보다 작은 값과 큰 값으로 나누는 파티션(partition)이라는 하위 프로시저를 사용하며, 이는 선형 시간 내에 수행된다. 퀵 정렬은 두 부분 리스트를 모두 재귀적으로 정렬하지만(최선의 경우 Ω(n log n) 시간 소요), Introselect는 필요한 값이 있는 부분 리스트만 재귀적으로 처리한다.

다음은 Introselect의 의사 코드이다.

```

'''function''' select(a, k, left, right)

'''loop'''

select a pivot value a[pivotIndex]

pivotNewIndex := partition(a, left, right, pivotIndex)

'''if''' k = pivotNewIndex

'''return''' a[k]

'''else if''' k < pivotNewIndex

right := pivotNewIndex-1

'''else'''

left := pivotNewIndex+1

```

퀵 정렬처럼 Introselect도 피벗 값 선택에 따라 성능이 달라진다. 일관되게 좋지 않은 피벗 값이 선택되면 성능이 저하될 수 있다. Introselect는 최악의 경우에도 O(n) 시간을 보장하기 위해 중앙값의 중앙값 알고리즘으로 전환(fallback)하는 방식을 사용한다.

3. 3. 팩토리 기반 알고리즘

가장 적은 비교 횟수를 갖는 결정적 선택 알고리즘은

k

값이

1

또는

n

에서 멀리 떨어져 있을 때, 1976년 아놀드 쇤하게, 마이크 패터슨, 닉 피펜저(spp)에 의해 소개된 '팩토리(factories)' 개념에 기반을 둔다. 이들은 비교를 사용하여 작은 부분 순서를 결합함으로써, 입력 값의 작은 부분 집합에 대해 특정 유형의 부분 순서를 구축하는 방법이다. 아주 간단한 예로, 한 유형의 팩토리는 단일 요소 부분 순서의 시퀀스를 입력으로 받아, 이 순서의 요소들을 쌍으로 비교하고, 두 요소의 완전 정렬 집합 시퀀스를 출력으로 생성할 수 있다. 이 팩토리의 입력으로 사용되는 요소는 아직 어떤 것과도 비교되지 않은 입력 값이거나, 다른 팩토리에서 생성된 "폐기" 값일 수 있다. 팩토리 기반 알고리즘의 목표는 다양한 팩토리를 결합하여, 일부 팩토리의 출력을 다른 팩토리의 입력으로 사용하여, 결국 하나의 요소(

k

번째로 작은 값)가 다른

k-1

개의 요소보다 크고, 또 다른

n-k

개의 요소보다 작은 부분 순서를 얻는 것이다. 이러한 팩토리의 신중한 설계는 중앙값 찾기에 적용될 때 최대

2.942n

개의 비교를 사용하는 알고리즘으로 이어진다. 다른

k

값의 경우, 비교 횟수는 더 적다.

3. 4. 병렬 알고리즘

레슬리 밸리언트는 1975년부터 선택 알고리즘의 병렬 알고리즘을 연구하면서, 이러한 알고리즘을 분석하기 위해 병렬 비교 트리 모델을 도입했다. 밸리언트는 이 모델에서 선형 개수의 비교를 사용한 선택은 최소값 또는 최대값을 선택하는 경우에도

\Omega(\log\log n)

병렬 단계를 필요로 한다는 것을 증명했다.^[1] 이후 연구자들은

O(\log\log n)

단계에서 선택을 위한 병렬 알고리즘을 발견하여 이 경계에 일치시켰다. 임의의 병렬 비교 트리 모델에서는 제한된 단계 수와 선형 개수의 비교로 선택을 수행할 수 있다.

보다 현실적인 병렬 RAM 컴퓨팅 모델(배타적 읽기 배타적 쓰기 메모리 접근)에서는

O(n/\log n)

개의 프로세서를 사용하여

O(\log n)

시간에 선택을 수행할 수 있으며, 이는 시간과 프로세서 수 모두에서 최적이다. 동시 메모리 접근을 사용하면 일반적으로 약간 더 빠른 병렬 시간을 사용할 수 있으며, 시간 경계의

\log n

항을

\log k

로 대체할 수 있다.

3. 5. 부분 선형 자료 구조

데이터가 이미 자료 구조로 구성되어 있는 경우, 값의 수에 대해 부분 선형적인 시간 내에 선택을 수행할 수 있다.

정렬된 배열: 이미 배열로 정렬된 데이터의 경우, $k$ 번째 요소를 선택하는 것은 단일 배열 조회로 상수 시간 내에 수행될 수 있다. 정렬된 행과 열이 있는 크기 $m \times n$ 의 2차원 배열의 경우, 선택은 $O(m \log(2n/m))$ 시간 내에 수행될 수 있으며, $k$ 가 배열 차원에 비해 작을 때는 더 빠르게 수행될 수 있다. $m$ 개의 1차원 정렬된 배열 모음에서 선택된 항목보다 $i$ 번째 배열에 $k_i$ 개의 항목이 작은 경우, 시간은 $O(m + \sum_{i=1}^m \log(k_i + 1))$ 이다.
이진 힙: 이진 힙의 데이터에서 선택은 $O(k)$ 시간이 소요된다. 이는 힙의 크기 $n$ 과 무관하며, 최선 우선 탐색에서 얻을 수 있는 $O(k \log n)$ 시간 제한보다 빠르다. 이 방법은 힙 정렬 트리(각 노드가 자식보다 작은 값을 갖는 하나의 값을 저장하는 트리)로 구성된 데이터에 일반적으로 적용될 수 있다.
순서 통계 트리: 동적 삽입 및 삭제가 발생하는 데이터 값 모음의 경우, 순서 통계 트리는 균형 이진 탐색 트리 구조를 트리의 노드당 일정량의 추가 정보로 보강하여, 삽입, 삭제 및 선택 쿼리를 모두 작업당 $O(\log n)$ 시간 내에 수행할 수 있도록 한다.

4. 하한

$n$ 개의 값 중 최솟값을 선택하려면 $n-1$ 번의 비교가 필요하다. 선택되지 않은 $n-1$ 개의 값은 각각 어떤 비교에서 가장 큰 값으로 판명되어야 하기 때문이다. 동일한 논리가 최댓값 선택에도 적용된다.

두 번째로 작은 값을 선택하는 경우, 1964년 소련의 수학자 세르게이 키슬리친이 엄밀한 하한을 발표했다. 최소값과 비교된 $p$ 개 항목 각각은 두 번째로 작은 값의 후보이며, 이 값을 제거하려면 $p-1$ 개가 다른 값보다 커야 한다. 따라서 최소 $n+p-2$ 번의 비교가 필요하다. 대립 논증은 $p$ 가 $\log_2 n$ 이 되도록 강제할 수 있음을 보여준다. 따라서 두 번째로 작은 값을 선택하는 데 필요한 최악의 경우 비교 횟수는 $n+\lceil\log_2 n\rceil-2$ 이다.

더 일반적으로, $k$ 번째 요소를 $n$ 개 중에서 선택하는 데 평균적인 경우 최소 $n+\min(k,n-k)-O(1)$ 번의 비교가 필요하다. 야오의 원리에 따르면, 이는 최악의 경우 입력에 대한 무작위 알고리즘의 예상 비교 횟수에도 적용된다.

결정론적 알고리즘의 경우, $k$ 번째 요소를 선택하는 데 $\bigl(1+H(k/n)\bigr)n+\Omega(\sqrt n)$ 번의 비교가 필요하다. 여기서 $H(x)=x\log_2\frac1x + (1-x)\log_2\frac1{1-x}$ 는 이진 엔트로피 함수이다. 중앙값 찾기의 특별한 경우는 비교 횟수에 대한 약간 더 큰 하한, 최소 $(2+\varepsilon)n$ 을 가진다.

도널드 커누스는 ''The Art of Computer Programming''에서 ''k''번째로 작은 요소를 ''n''개의 요소에서 선택하는 데 필요한 비교 횟수의 하한을 논하고 있다. 최댓값 또는 최솟값을 구하는 데 필요한 비교 횟수의 하한은 n − 1이다. ''k''번째로 작은 값을 구하려면 적어도 다음 횟수의 비교가 필요하다.

: $n - k + \sum_{n+1-k < j \leq n} \lceil{\log_2 j}\rceil$

5. 언어 지원

일반적으로 선택 알고리즘에 대한 내장 지원을 제공하는 언어는 거의 없지만, 대부분 목록에서 가장 작거나 큰 요소를 찾는 기능은 제공한다. C++의 표준 템플릿 라이브러리는 예상되는 선형 시간을 보장하는 템플릿화된 `nth_element` 메서드를 제공한다. 파이썬 표준 라이브러리에는 정렬된 순서로 컬렉션에서 가장 작거나 큰 요소를 반환하는 `heapq.nsmallest` 및 `heapq.nlargest` 함수가 포함되어 있다.^[1] 2017년부터 매트랩은 벡터에서 최대 (최소) k개의 값과 해당 인덱스를 반환하는 `maxk()` 및 `mink()` 함수를 포함하고 있다.

C++는 `nth_element` 메서드 템플릿을 가지고 있어, 선형 시간 내의 선택을 기대할 수 있음을 보장한다. 또한, C++는 `partial_sort` 알고리즘도 제공하며, k개의 최소 요소를 정렬된 상태로 선택하는 처리를 O(nlogk) 시간에 수행한다.

Perl은 CPAN에서 n개의 요소를 선택하는 함수군을 제공하는 `Sort::Key::Top` 모듈을 제공한다.

정렬 알고리즘의 언어 지원이 더 많기 때문에, 실제로는 (성능 면에서 불리하지만) 단순히 정렬을 수행한 후 선택하는 방법이 많이 사용된다.

6. 역사

퀵셀렉트는 토니 호어가 1965년에 처음 제시했으며^[1], 도널드 커누스가 1971년 기술 보고서에서 처음 분석했다. 최초의 알려진 선형 시간 결정적 선택 알고리즘은 중앙값의 중앙값 방법으로, 1973년 마누엘 블룸, 로버트 플로이드, 본 프랫, 론 리베스트, 로버트 타잔이 발표했다. 이들은 선택 문제의 공식화를 루이스 캐럴로 더 잘 알려진 찰스 L. 도지슨의 연구(1883년 단일 제거 스포츠 토너먼트의 일반적인 디자인이 두 번째로 좋은 선수가 2위를 차지하는 것을 보장하지 않는다고 지적)와, 휴고 스타인하우스의 연구(1930년경 최소한의 경기 수(비교)로 이 보장을 할 수 있는 토너먼트 디자인을 요구)로 추적한다.

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com