전체 정렬 없이 지금 가장 중요한 항목만 빠르게 꺼내는 구조
항상 최솟값이나 최댓값 하나만 필요할 때 전체를 매번 정렬하는 것은 낭비입니다. 힙은 가장 우선인 값의 빠른 접근과 삽입을 균형 있게 제공합니다.
코드를 생각하지 말고, 아래 상황이 어떤 순서로 움직이는지만 따라가 보세요.
먼저 온 감기 환자가 있어도 방금 온 위급 환자를 먼저 진료할 수 있습니다.
모든 할 일을 완벽히 정렬하기보다 마감이 가장 가까운 일 하나를 계속 골라 처리합니다.
코딩 테스트의 장난감 예제를 넘어, 실제 시스템에서 같은 원리가 어디에 숨어 있는지 연결해 보세요.
실행 시각이나 우선순위가 가장 앞선 작업을 꺼냅니다.
스트리밍 데이터에서 가장 큰 K개만 작은 힙에 유지합니다.
다익스트라에서 현재까지 거리가 가장 짧은 정점을 선택합니다.
접수 순서와 무관하게 가장 위급한 환자를 먼저 진료합니다.
검색량이 높은 상위 항목만 계속 유지해 순위를 갱신합니다.
최소 힙에서는 부모가 자식보다 작거나 같습니다. 완전 이진 트리를 배열에 저장하며, 삽입·삭제 후 위아래로 교환해 규칙을 복구합니다. peek는 O(1), push/pop은 O(log n)입니다.
| 연산 | Python 표현 | 시간 |
|---|---|---|
| 힙 만들기 | heapq.heapify | O(n) |
| 삽입 | heappush | O(log n) |
| 최솟값 제거 | heappop | O(log n) |
| 최솟값 보기 | heap[0] | O(1) |
heap = [3]부모 3과 교환 → heap = [1, 3]부모 1보다 크므로 heap = [1, 3, 2]1 제거 후 복구 → heap = [2, 3]설명을 닫고 먼저 풀어본 뒤, 막히는 지점에서 어떤 연산이 필요한지 다시 떠올려 보세요.
Easy 연습 1 / 7
Python으로 풀기Easy 연습 2 / 7
Python으로 풀기Easy 연습 3 / 7
Python으로 풀기Easy 연습 4 / 7
Python으로 풀기Easy 연습 5 / 7
Python으로 풀기Easy 연습 6 / 7
Python으로 풀기Easy 연습 7 / 7
Python으로 풀기Medium 연습 1 / 3
Python으로 풀기Medium 연습 2 / 3
Python으로 풀기Medium 연습 3 / 3
Python으로 풀기