[선택 알고리즘] - QuickSelect

알고리즘 설명

Quickselect 알고리즘은 k번째 원소를 찾는 알고리즘입니다. 일반적으로 정렬되지 않은 리스트에서 k번째로 작은 원소를 찾는 데 사용됩니다. 물론, 정렬된 리스트에서도 사용할 수 있습니다.

평균적으로 "O(n)"의 시간 복잡도를 가지며, 최악의 경우 "O(n^2)"의 시간 복잡도를 가집니다. 하지만 이런 경우는 매우 드뭅니다. 따라서 일반적인 정렬 알고리즘보다 효율적인 방법입니다.

 

알고리즘 동작 방식

1. 리스트에서 임의의 원소를 피벗으로 선택합니다.
2. 리스트를 피벗을 기준으로 분할하여, 피벗보다 작은 원소는 왼쪽, 큰 원소는 오른쪽에 위치시킵니다.
3. k번째로 작은 원소가 왼쪽에 위치해 있으면, 왼쪽 부분 리스트에서 Quickselect 알고리즘을 재수행합니다.
4. k번째로 작은 원소가 오른쪽에 위치해 있으면, 오른쪽 부분 리스트에서 Quickselect 알고리즘을 재수행합니다.
5. k번째로 작은 원소가 피벗과 같으면, 피벗을 반환합니다.

 

Python 코드

import random

def quickselect(arr, k):
    # 재귀 종료 조건
    if len(arr) == 1:
        return arr[0]

    # 피벗을 랜덤하게 선택합니다.
    pivot = random.choice(arr)

    # 피벗을 기준으로 배열을 분할합니다.
    left = [x for x in arr if x < pivot]
    mid = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]

    # k번째로 작은 원소가 왼쪽에 있으면, 왼쪽 부분 배열에서 재귀적으로 호출합니다.
    if k < len(left):
        return quickselect(left, k)

    # k번째로 작은 원소가 오른쪽에 있으면, 오른쪽 부분 배열에서 재귀적으로 호출합니다.
    elif k < len(left) + len(mid):
        return mid[0]
    else:
        return quickselect(right, k - len(left) - len(mid))

# 예제
arr = [3, 1, 4, 1, 5, 9, 2, 6, 5]
k = 4
result = quickselect(arr, k)
print(f"배열에서 {k+1}번째로 작은 원소는 {result}입니다.")

 

Python 코드 풀이

1. random()을 사용하여 임의의 원소를 피벗으로 지정합니다.
2. 피벗을 기준으로 리스트를 분할하여, 피벗보다 작은 원소는 왼쪽, 큰 원소는 오른쪽에 위치시킵니다.
3. k번째로 작은 원소가 왼쪽에 위치하면, 왼쪽 부분에서 재귀 호출하여 Quickselect 알고리즘을 재수행합니다.
4. k번째로 작은 원소가 오른쪽에 위치하면, 오른쪽 부분에서 재귀 호출하여 Quickselect 알고리즘을 재수행합니다.
5. k번째로 작은 원소가 피벗과 같으면 그 값을 반환합니다.

 

이렇게 Quickselect 알고리즘을 이해하고 Python으로 구현해보면 어렵지 않게 k번째 작은 원소를 찾을 수 있습니다. 이해가 안 가시는 부분이 있다면 언제든 질문해주세요!