▶ 선택문제(Selection)란?
※ 선택 정렬(Selection Sort)과는 다른 알고리즘입니다.
선택(Selection) 문제는 n개의 숫자들 중에서 k번째로 작은 숫자를 찾는 문제입니다.
이 문제를 해결하기 위한 단순한 방법은 다음과 같습니다.
1) 최소 숫자를 k번 찾는다.
→ 숫자 n개가 들어있는 배열 중에서 최소 숫자를 찾고, 찾을 때마다 입력에서 그 숫자를 제거합니다.
시간복잡도는 O(kn), k번째 숫자를 찾을 때까지 반복하는 과정마다 항상 n, n-1, n-2....(최소 숫자는 제거되므로) 개의 숫자들을 탐색하기 때문입니다.
2) 숫자들을 정렬한 후, k번째 숫자를 찾는다.
→ 시간복잡도는 O(nlogn), 즉 정렬하는 과정에서 걸리는 시간에 따라 다를 것입니다. (k번째 숫자를 찾는 것은 상수시간)
▶ 아이디어
- 이진 탐색
정렬된 입력의 중간에 있는 숫자와 찾고자 하는 숫자를 비교함으로써, 입력을 1/2로 나눈 두 부분 중에서 한 부분만을 검색합니다.
찾고자 하는 숫자가 만약에 25이고, 중간에 있는 숫자가 10이라면, 입력을 1/2로 나누었을 때, 오른쪽 부분만을 탐색하면 됩니다.
Small group은 피봇보다 작은 숫자의 그룹이고, Large group은 피봇보다 큰 숫자의 그룹 이렇게 둡니다.
이렇게 분할했을 때 알아야할 것은 각 그룹의 크기 즉, 숫자의 개수를 알아야 합니다.
각 그룹의 크기를 알면, k번째 작은 숫자가 어느 그룹에 있는지 알 수 있습니다. 또 그 그룹에서 몇 번째로 작은 숫자를 찾아야하는지도 알 수 있습니다.
예를 들자면, 아래와 같은 배열이 있습니다. 이때 피봇은 20으로, 찾고자 하는 숫자는 7번째 작은 숫자라고 가정합니다.
Small group의 크기는 4, Large group의 크기는 5.
크기를 알면, 7번째의 숫자가 Large group에 있다는 사실을 알 수 있습니다.
이때 Large group에서 몇 번째 숫자를 찾아야 할까요?
| 4 | 14 | 3 | 7 | 20 | 24 | 25 | 35 | 28 | 31 |
- Small group에 k번째 작은 숫자가 있는 경우
→ k번째 작은 숫자를 Small group에서 찾습니다.
- Large group에 k번째 작은 숫자가 있는 경우
→ (k - small group의 크기 - 1)번째로 작은 숫자를 Large group에서 찾아야 합니다.
(이때 1은 피봇에 해당됩니다.)
이제 위 질문의 답을 한다면, Large group에서 7 - 4 - 1 = 2, 바로 2번째 숫자를 찾아야 합니다.
▶ 선택 문제의 수도코드
Selection(A, left, right, k)
입력: A[left] ~ A[right] 와 k, (단, 1<= k <= |A|, |A| = right - left + 1)
출력: A[left] ~ A[right]에서 k번재 작은 원소
1. 피봇을 A[left] ~ A[right]에서 랜덤하게 선택하고, 피봇과 A[left]의 자리를 바꾼 후, (첫 번째가 아닌 값을 피봇으로 정하면, 그 피봇이 원래 있던 위치를 지나갈 수 있으므로 맨 앞으로 빼놓는 것.) 피봇과 배열의 각 원소를 비교하여 피봇보다 작은 숫자는 A[left] ~ A[p - 1]로 옮기고, 피봇보다 큰 숫자는 A[p+1] ~ A[right]로 옮기며, 피봇은 A[p]에 놓는다.
2. S = (p - 1) - left + 1 // S = Small group의 크기
3. if (k <= S) Selection(A, left, p-1, k) // Small group에서 찾기
4. else if ( k = S + 1) return A[p] //피봇 = k번째 숫자
5. else Selection(A, p + 1, right, k - S - 1) // Large group에서 찾기
1. 퀵 정렬에서 하던 partition의 과정을 그대로 수행하면 됩니다.
2. 분할 과정이 다 끝나면, Small group의 크기를 알아냅니다.
3. 만약 k가 S, 즉 Small group의 크기보다 작다면, Small group에 대한 Selection 함수를 호출합니다.
4. 만약 k가 S + 1, 피봇의 위치와 같다면 피봇을 return 합니다.
5. 둘 다 아니라면, k번째 작은 숫자는 Large group에 있는 것이니깐 Large group에 대한 Selection 함수를 호출합니다.
퀵 정렬의 partition 과정이 궁금하다면 이 게시물을 참고하세요
▶ 선택 문제의 파이썬 코드
from random import randint
def partition(arr, left, right):
pi = randint(left, right)
if pi != left:
arr[pi], arr[left] = arr[left], arr[pi]
p = left + 1
q = right
while True:
while p < right and arr[p] < arr[left]:
p += 1
while q > left and arr[q] > arr[left]:
q -= 1
if p >= q:
break
arr[p], arr[q] = arr[q], arr[p]
p +=1
q -=1
arr[left], arr[q] = arr[q], arr[left]
return q
def selection(arr, left, right, k):
pivot = partition(arrr, left, right)
sgs = pivot - left
if k < sgs:
return selection(arr, left, pivot - 1, k)
elif k == sgs:
return arr[pivot]
else:
return selection(arr, pivot + 1, right, k - pivot - 1)
#sublist는 숫자들이 있는 리스트입니다.
k = 6
value = selection(sublist, 0, len(sublist) - 1, k - 1)
▶ 선택 문제의 수행 과정
아래는 k = 7번째 작은 숫자를 찾는 과정입니다.
먼저 Selection(A, 0, 11, 7)을 호출해서, 전체 A 배열을 피봇 8을 기준으로 분할합니다.
Small group의 크기인 S = (p - 1) - left + 1 = 3 - 0 + 1 = 4
k > S 이므로 Selection(A, p + 1, right, k - S - 1) = Selection(A, 5, 11, 2) 을 호출합니다.
즉, Large group에서 두 번째 작은 숫자를 찾으러 갑니다.
Selection(A, 5, 11, 2)를 호출해서 피봇 A[11]의 14를 기준으로 분할합니다.
S = (p - 1) - left + 1 = 4, Small group의 크기는 4입니다.
k < S 이므로, Small group에 대해서 Selection 함수를 호출합니다.
Selection(A, 5, 8, 2)를 호출합니다.
즉, Small group에서 두 번째로 작은 숫자를 찾으면 됩니다.
피봇인 A[5], 10을 기준으로 분할합니다.
분할을 했더니, k = p(피봇의 위치)가 True이므로, k = 7번쩨 작은 수로, A[6] = 10을 해로 return합니다.
▶ Selection 알고리즘 고려 사항
- Selection 알고리즘은 분할 정복 알고리즘이기도 하지만, 랜덤 알고리즘
→ 피봇을 랜덤하기 정하기 때문
- 피봇이 입력을 너무 한쪽으로 치우치게 분할한다면
→ 즉, |Small group| << |Large group| 또는 |Small group| >> |Large group| (|group|은 group의 크기) 일 때에는 알고리즘의 수행 시간이 길어집니다. 퀵 소트때도 언급한 이야기죠.
- 선택 알고리즘이 호출될 때마다 입력을 한쪽으로 치우치게 분할될 확률은?
→ 마치 동전을 던질 때 한쪽 면이 나오는 확률과 동일
▶ good / bad 분할
- good 분할과 bad 분할의 정의
분할된 두 그룹 중의 하나의 크기가 입력 크기의 3/4과 같거나 그보다 크게 분할하면 나쁜(bad) 분할이라고 정의합니다.
반대의 경우는 좋은 (good) 분할입니다.
예를 들어 다음과 같이 16개의 숫자가 있다면,
1 ~ 4, 13 ~ 16 사이의 숫자를 피봇으로 고른다면, Bad 분할, 5~ 12사이의 숫자를 고른다면, Good 분할이 됩니다.
good 분할이 되는 피봇을 선택할 확률과 bad 분할이 되는 피봇을 선택할 확률이 각각 1/2로 동일합니다.
그래서 위에서 한 쪽으로 치우치게 분할할 확률이 동전 한 쪽 면이 나오는 확률과 동일하다고 한 것입니다.
▶ Selection의 시간 복잡도
피봇을 랜덤하게 정했을 때 good 분할이 될 확률이 1/2이므로 평균 2회 연속해서 랜덤하게 피봇을 정하면 good 분할을 할 수 있습니다.
그렇다면, 2회 연속해서 피봇을 정하면 무조건 good 분할을 한다는 가정하에, good 분할의 연속하여 이루어졌을 때만의 시간 복잡도를 구하여, 그 값에 2를 곱하면 평균 경우 시간 복잡도를 얻을 수 있습니다.
입력 크기가 n에서부터 3/4배로(최대 3/4 크기고, 실제로는 3/4보다 작은 크기일 수도 있음 편의상 3/4이라고 지칭) 연속적으로 감소되고, 크기가 1일 때에는 더 이상 분할할 수 없습니다.
Selection함수에서는 O(입력크기)의 시간 복잡도를 가지므로, Selection 알고리즘의 시간 복잡도는 각 Selection함수 호출마다 걸린 시간을 다 더한 것의 시간 복잡도입니다.
따라서 Selection의 알고리즘은 평균 2회에 good 분할이 되므로 2x O(n) = O(n) 입니다.
▶ 선택 알고리즘과 이진 탐색
- 유사성
→ 이진 탐색은 분할과정을 진행하면서 범위를 1/2씩 좁혀가며 찾고자 하는 숫자를 탐색
→ 선택 알고리즘은 피봇으로 분할하여 범위를 좁혀감
- 공통점
→ 부분 문제들을 취합하는 과정이 별도로 필요 X
▶ 선택 알고리즘 활용
데이터 분석을 위한 중앙값(median)을 찾는데 활용
데이터 분석에서 평균값도 유용하지만, 중앙값이 더 설득력 있는 데이터 분석을 제공
예를 들어, 대부분의 데이터가 1이고, 오직 1개의 숫자가 매우 큰 숫자 (노이즈 (noise), 잘못 측정된 데이터) 이면,
평균값은 매우 왜곡된 분석
참고: 알기 쉬운 알고리즘(양성봉)
'Algorithm > Divide-and-Conquer' 카테고리의 다른 글
| [알고리즘 공부] 최근접 점의 쌍 찾기 알고리즘(Closest Pair of Points) - python 파이썬 (0) | 2021.10.21 |
|---|---|
| [ 알고리즘 공부 ] 퀵정렬 퀵소트(Quick Sort) - 분할 정복 알고리즘(feat. python 파이썬) (0) | 2021.10.06 |
| [ 알고리즘 공부 ] 합병 정렬(Merge Sort) 알고리즘 - 분할 정복 알고리즘(python, 파이썬) (2) | 2021.10.01 |
