4. k번째 값만 필요하면 전부 정렬하지 않는다
해설글
작성 · 3분 읽기 · 조회수 —수정
기초 개념과 예제를 보강하고 시리즈 흐름을 연결
필요한 답은 하나뿐이었다
정렬했을 때 앞에서 k번째에 놓이는 값을 k번째 작은 값, 또는 순서 통계량이라고 한다. k=1이면 최솟값이고 k=n이면 최댓값이다. 배열 인덱스가 0부터 시작해도 문제의 k는 보통 1부터 센다는 차이를 먼저 고정해야 한다.
예를 들어 [7, 2, 9, 4, 2]를 정렬하면 [2, 2, 4, 7, 9]다. 세 번째 작은 값은 4다. 중복된 2도 각각 한 자리를 차지한다. 답 하나만 필요하다면 다섯 값을 끝까지 정렬하지 않고, 최소 힙에서 루트를 세 번 꺼낼 수 있다.
최소 힙은 모든 부모가 자식보다 작거나 같은 완전이진트리다. 루트가 현재 최솟값이므로 extract-min은 루트를 저장하고, 마지막 원소를 루트로 옮긴 뒤 down-heap해 다음 최솟값을 준비한다.
1001 과제 노트의 질문은 전체 배열을 정렬하는 문제가 아니었다. 배열에서 k번째로 작은 값 하나를 찾아야 했다. 노트에는 해결 과정이 두 덩어리로 정리되어 있다.
O(n) = 배열 L을 복사해서 H에 담은 후 최소 힙 구성 시 연산시간
O(k log n) = K번째가 나올 때까지 추출하는 연산시간
처음에는 정렬한 뒤 arr[k-1]을 읽는 방법이 가장 곧게 보인다. 하지만 나머지 원소들의 정확한 순서는 답에 필요하지 않다. 최소 힙은 전체 순서를 만드는 대신 현재 최솟값만 루트에 보장한다.
힙을 만들고 필요한 만큼만 꺼낸다
저장소의 1001-reprot.c는 원본을 보존하기 위해 길이 n의 배열 H를 만들고 L을 복사한다. 그 뒤 bottom-up 방식으로 최소 힙을 만든다.
예를 들어 [7, 2, 9, 2, 5, 1]에서 네 번째 작은 값을 찾는다고 하자. 최소 힙의 루트는 1이다. 루트를 세 번 제거하면 1, 2, 2가 빠지고, 새 루트 5가 네 번째 값이 된다. 힙 내부의 나머지 원소가 완전히 정렬되어 있을 필요는 없다.
| 현재 순위 | 꺼내거나 읽은 루트 | 다음에 남는 최솟값 |
|---|---|---|
| 1 | 1 제거 | 2 |
| 2 | 2 제거 | 2 |
| 3 | 2 제거 | 5 |
| 4 | 5를 답으로 읽음 | - |
코드가 k번 제거하지 않고 k-1번만 제거하는 이유도 이 표에 있다. 앞의 값만 치우면 k번째 값은 이미 루트에 있으므로 마지막에는 읽기만 하면 된다.
for (int count = 1; count < k; count++) {
heap[0] = heap[--heap_size];
down_heap(heap, heap_size, 0);
}
return heap[0];
상향식 힙 생성은 O(n)이고 한 번의 제거와 복구는 O(log n)이다. k번째 값을 루트로 만들려면 앞의 k-1개를 제거하므로 전체 시간은 O(n + k log n)이다. 원본 보존을 위한 복사 힙은 O(n) 추가 공간을 쓴다.
k의 크기가 선택을 바꾼다
k가 1이면 힙을 만든 직후 끝난다. 반면 k가 n에 가까우면 거의 모든 값을 꺼내므로 O(n log n)에 가까워진다. “전체 정렬을 하지 않는다”는 말이 언제나 압도적으로 빠르다는 뜻은 아니다. 필요한 순위가 어디인지, 원본을 보존해야 하는지, 여러 k 질의가 이어지는지에 따라 선택이 달라진다.
최댓값 쪽이 더 가까운 경우 최대 힙으로 n-k+1번째를 찾는 대칭적인 방법도 있다. 평균 O(n)의 Quickselect도 비교 대상이다. 이 글의 목표는 최소 힙이 항상 최선이라고 결론 내리는 것이 아니라, 답에 필요하지 않은 순서를 만들지 않는 사고를 확인하는 데 있다.
이번에 범위까지 확인한 코드
원본 과제 코드는 정해진 유효 입력만 사용한다. 범용 함수로 가져오려면 n > 0, 1 <= k <= n, 메모리 할당 성공을 먼저 확인해야 한다. k가 0이면 “앞에서 k-1번 제거”라는 의미 자체가 깨지고, k가 n보다 크면 빈 힙을 읽게 된다.
별도의 재현 코드에서는 위의 중복 포함 배열을 사용했다. qsort로 만든 참조 배열과 k=1부터 6까지의 결과를 모두 대조했고 k=1..6: ok를 확인했다. 이 검증은 이번에 작성한 코드의 결과다. 과제 노트에 있던 과거 실행 화면이나 시간을 새로 재현했다고 말하는 것은 아니다.
노트의 식은 단순한 복잡도 계산에서 한 걸음 더 나아간다. 원하는 출력이 하나라면 전체 순서라는 더 강한 결과를 굳이 만들 필요가 없다. 알고리즘을 고를 때는 입력 크기뿐 아니라 필요한 답의 크기 k도 함께 봐야 한다.
참고한 기록과 코드
- 개인 노트 「1001 알고리즘 과제」, 2025-10-01
1001-reprot.c