위키득계정 ↗
기술

상위 K개 선택과 전체 정렬

상위 K개 선택과 전체 정렬기술
입력 크기
N개
선택 개수
K개
작은 K의 방법
최소 힙으로 큰 값 후보 유지
추가 확인
동점 처리와 최종 출력 순서
큰 값 몇 개만 필요한 문제에서는 모든 항목의 순서를 구할 필요가 없다. 필요한 결과의 개수와 출력 순서, 입력이 계속 들어오는지를 따져 전체 정렬과 제한된 크기의 힙을 선택한다.

결과가 요구하는 정보

점수 백만 개에서 높은 점수 열 개만 찾는 일과 모든 점수에 순위를 붙이는 일은 요구하는 정보량이 다르다. 전자는 선택되지 않은 나머지 점수의 상대 순서를 알아도 결과가 달라지지 않는다. 구현 전에 필요한 것이 항목의 집합인지, 정렬된 목록인지, 경계 점수인지 정하면 불필요한 작업을 줄일 수 있다.

후보만 유지하는 과정

큰 값 세 개를 유지한다고 하자. 후보를 최소 힙에 넣으면 후보 가운데 가장 작은 값이 루트에 놓인다. 후보가 가득 찬 뒤 새 값이 루트보다 크면 작은 후보를 빼고 새 값을 넣는다. 예를 들어 현재 후보가 12, 17, 21이고 19가 들어오면 12가 탈락한다. 이것은 입력 전체를 정렬하는 과정과 다르다.

시간과 메모리

비교 비용을 일정하다고 보는 일반적인 분석에서 크기 K인 힙을 이용한 선택은 O(N log K) 시간과 후보 O(K) 공간으로 처리할 수 있다. 후보까지 내림차순으로 출력하려면 별도 정렬 비용이 붙는다. K가 N에 가까우면 전체 정렬이 단순하고 실제 실행에서도 유리할 수 있으므로 복잡도 식 하나로 모든 크기의 선택을 결정하지 않는다.

경계 조건과 동점

K가 0이면 빈 결과를 반환할지 입력 오류로 볼지 정한다. K가 입력보다 큰 경우도 계약을 정해야 한다. 같은 점수 가운데 먼저 들어온 항목을 우선할지, 식별자 순서를 적용할지에 따라 비교 키가 달라진다. 점수만 저장했다가 나중에 원래 항목을 찾으려 하면 중복 점수 때문에 원하는 결과를 복원하기 어려울 수 있다.

선택과 표현의 분리

선택용 힙의 내부 배열을 그대로 보여 주면 전체가 정렬된 것처럼 보장되지 않는다. 후보를 유지하는 구조와 사용자에게 보여 주는 순서를 분리한다. 입력이 계속 들어오는 상황에서는 새 항목마다 모든 데이터를 다시 정렬하는 대신 후보를 갱신할 수 있지만, 삭제나 점수 수정까지 요구되면 추가 설계가 필요하다.

관련 문서

우선순위 큐와 정렬 / 시간 복잡도와 실제 실행 시간 / 알고리즘