힙 문제 풀이에서 가장 중요한 것은 구현법보다 문제를 보는 기준입니다. 많은 문제를 정렬로도 풀 수 있어서, heap을 왜 따로 배워야 하는지 처음에는 감이 잘 안 올 수 있습니다.
하지만 전체를 한 번 정렬하는 문제와, 가장 작은 값이나 가장 큰 값을 계속 꺼내야 하는 문제는 완전히 다릅니다. 이번 글에서는 이 차이를 코딩테스트 기준으로 정리하고, 정렬보다 heap이 먼저 떠오르는 문제 신호까지 함께 보겠습니다.
힙은 무엇이고 우선순위 큐는 무엇일까
힙은 부모-자식 관계에 따라 최솟값이나 최댓값이 위로 올라오도록 정리된 트리 구조입니다. 우선순위 큐는 그 힙을 이용해 가장 우선순위가 높은 값을 빠르게 꺼내는 자료구조로 생각하면 됩니다.
즉 중요한 것은 “전체가 완전히 정렬돼 있느냐”가 아니라, 지금 당장 필요한 최솟값이나 최댓값을 빠르게 꺼낼 수 있느냐입니다.
정렬보다 heap이 먼저 떠오르는 순간
- 최소값이나 최대값을 여러 번 반복해서 꺼낸다
- 데이터가 한 번에 다 주어지지 않고 계속 들어온다
- 상위 K개만 유지하면 된다
- 매 단계마다 가장 우선순위가 높은 작업을 처리해야 한다
이런 문제에서 전체 정렬을 매번 다시 하면 낭비가 커집니다. 이때 heap은 필요한 원소만 빠르게 관리하는 데 유리합니다.
import heapq
heap = []
for x in [5, 2, 8, 1]:
heapq.heappush(heap, x)
while heap:
print(heapq.heappop(heap))Python heapq 공식 문서와 C++ priority_queue 설명을 같이 보면, 힙의 핵심이 전체 정렬이 아니라 top 원소를 빠르게 관리하는 데 있다는 점이 분명해집니다.
이 코드는 단순하지만, “지금 가장 작은 값이 무엇인가”를 계속 물어보는 문제에서 heap이 왜 자연스러운지 잘 보여줍니다.
상위 K개 문제에서 왜 특히 강할까
예를 들어 숫자가 계속 들어오는데 상위 10개만 유지하고 싶다면, 전체를 매번 정렬할 필요가 없습니다. 크기가 K인 힙만 유지하면 훨씬 효율적으로 풀 수 있습니다.
즉 heap은 정렬 자체가 목표가 아니라, 중간 과정에서 우선순위를 계속 관리해야 하는 문제에 잘 맞습니다.
자주 하는 실수
- heap으로 풀 수 있는 문제를 매번 전체 정렬로 푼다
- min heap과 max heap 방향을 헷갈린다
- 상위 K개 유지 문제에서 힙 크기 관리가 안 된다
- 정렬이 더 단순한 문제인데 heap을 억지로 쓴다
즉 heap은 만능이 아니라, “계속 가장 작은 것/큰 것을 뽑아야 하는가”라는 질문이 있을 때 특히 강합니다.
경계 판단은 이분 탐색 글, 반복 계산 최적화는 누적합 글과도 문제 풀이 감각이 이어집니다.
마무리
힙 문제 풀이의 핵심은 자료구조 이름을 외우는 것이 아니라, 전체를 정렬할 문제인지 아니면 우선순위를 유지하며 계속 꺼낼 문제인지를 구분하는 일입니다.
즉 정렬 대신 heap이 먼저 떠오르는 순간은, 필요한 원소를 반복해서 빠르게 선택해야 할 때입니다.
