Top K Selection: 상위 K개 원소
Top K, Top-K, 상위 K, K th largest
정의
배열 또는 스트림에서 상위 K 개 원소를 뽑는 문제.
접근 방법
1. 정렬 후 자르기
O(N log N). K 가 작을 때 낭비 심함.
2. Min-Heap (크기 K)
priority_queue<int, vector<int>, greater<>> pq;
for (int x : arr) {
pq.push(x);
if ((int)pq.size() > K) pq.pop();
}
// pq 안의 원소가 상위 KO(N log K). 스트리밍에도 적합.
3. Quickselect (offline)
Pivot 기반 partition, 원하는 위치 도달할 때까지 재귀. 평균 O(N), 최악 O(N²).
4. Introselect
Median-of-medians 로 pivot 선택. 최악 O(N) 보장. C++ std::nth_element 가 이 계열.
💬 댓글