20250102 / Unity_6차 17주차 목요일
n명의 NPC 중 특정 위치에서 가장 가까운 k명을 뽑기 위해 알고리즘을 찾던 중
Quickselect라는 것을 알게 되었다.
Quickselect의 작동 원리
- 피벗(Pivot) 선택:
- 리스트에서 임의의 값을 피벗으로 선택합니다.
- 파티셔닝(Partitioning):
- 피벗보다 작은 값은 왼쪽으로, 피벗보다 큰 값은 오른쪽으로 이동합니다.
- QuickSort와 동일한 방식으로 동작합니다.
- 필요한 부분만 탐색:
- 피벗의 위치를 기준으로, 필요한 부분(상위 N개 또는 k번째 요소가 포함된 부분)만 재귀적으로 탐색합니다.
- 예를 들어, 피벗이 상위 N개의 범위에 속하면, 더 이상의 재귀 호출 없이 종료합니다.
- 결과 반환:
- 특정 k번째 요소 또는 상위 N개 요소를 반환합니다.
보통의 방법은 전부 정렬하던 상위 k개까지 정렬하던 정렬하는 알고리즘이 들어가 있는데
이것은 정렬을 하지 않기 때문에 더 빠를 가능성이 있다.
가능성에서 그치는 이유는 Partitioning Pivot을 어떻게 잡느냐에 따라 성능이 뒤죽박죽이기 때문이다.
다른 방법과 비교하자면
1. LINQ를 이용한 간단한 구현
- LINQ의 OrderByDescending은 기본적으로 퀵소트(QuickSort)와 같은 비교 기반 정렬 알고리즘을 사용합니다.
- 전체 리스트를 정렬한 후 상위 N개의 요소를 선택하므로 O(n log n)이 시간 복잡도의 일반적인 경우입니다.
2. Min-Heap을 이용한 상위 N개 추출
- Min-Heap을 유지하면서 상위 N개 요소만 관리합니다.
- 각 요소를 추가/제거할 때마다 Min-Heap의 재구성이 필요하며, 이는 O(log k)입니다.
- 모든 요소를 순회하므로 총 시간 복잡도는 O(n log k)입니다.
3. Partitioning 알고리즘 (Quickselect)
- Quickselect는 정렬 대신 특정 피벗 값을 중심으로 필요한 부분만 탐색합니다.
- 평균 시간 복잡도는 O(n)입니다.
1번과 2번 방법은 일단 정렬이 이루어지기 때문에 시간 복잡도가 크게 변할 일이 없지만,
Quickselect 는 만약 미친 듯이 운이 좋아 한번에 k개로 분할된다면 O(k)의 시간 복잡도를 가지고
미친 듯이 운이 없어 pivot을 매번 최하위 값으로 뽑는다면 O(n²) 까지도 될 수 있다.