19 — 우선순위 큐(Priority Queue)

람다가 응급실 대기실에서 "어? 나보다 늦게 온 사람이 먼저 들어가네?"라고 발견하고, 제네릭이 "도착한 순서가 아니라 더 급한 사람을 먼저 부르는 거야!"라고 거들자, 돌핀쌤이 "도착 순서가 아니라 우선순위 순서로 꺼내는 게 바로 우선순위 큐예요. 지난 시간에 배운 힙으로 만든답니다"라고 안내하는 도입

🙋‍♀️ 람다: "선생님, 응급실에서 이상한 걸 봤어요. 분명 저보다 늦게 온 사람이 먼저 진료실에 불려 들어갔어요!"

🐬 돌핀쌤: "그건 순서가 뒤바뀐 게 아니에요. 응급실은 도착한 순서가 아니라 더 급한 사람을 먼저 부르거든요. 이렇게 도착 순서가 아니라 우선순위 순서로 꺼내는 자료구조를 우선순위 큐라고 해요. 지난 시간에 배운 힙으로 만든답니다!"

🎯 오늘 완성할 코드는?

오늘 만들 건 우선순위 큐예요. 값을 넣어 두면, 꺼낼 때 항상 가장 작은(가장 급한) 값부터 나오는 마법 상자랍니다. 파이썬의 heapq를 쓰면 단 몇 줄로 만들 수 있어요.

먼저 완성된 모습부터 볼게요. 지금은 이해 안 돼도 괜찮아요. 아래에서 한 줄씩 천천히 뜯어볼 거예요.

import heapq

heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 2)
heapq.heappush(heap, 8)
heapq.heappush(heap, 1)
print(heap)                 # [1, 2, 8, 5]
print(heapq.heappop(heap))  # 1
print(heapq.heappop(heap))  # 2
print(heapq.heappop(heap))  # 5
print(heapq.heappop(heap))  # 8

실행하면 이렇게 나와요.

[1, 2, 8, 5]
1
2
5
8

넣을 때는 5, 2, 8, 1 순서로 막 넣었는데, 꺼낼 때는 1, 2, 5, 8 작은 순서대로 나왔죠?

🐬 돌핀쌤: "정말 짧죠? 하지만 이 안에 우선순위 큐의 핵심이 다 들어 있어요. 지금부터 이 코드가 왜 항상 가장 작은 값을 먼저 꺼내 주는지 하나씩 풀어볼게요."

💡 어떻게 풀까? — 급한 사람 먼저 부르기

응급실을 떠올려 봐요. 응급도 숫자가 작을수록 더 위급하다고 정해 봅시다.

도착 순서        환자      응급도(작을수록 위급)
1번째 도착       두통        5
2번째 도착       심정지      1   ← 가장 위급
3번째 도착       골절        3

  ↓ 응급도가 작은 순서로 다시 줄 세우면 ↓

처리 순서: 심정지(1) → 골절(3) → 두통(5)

도착 순서와 상관없이 숫자가 작을수록 먼저 처리돼요. 람다가 본 응급실 풍경이 바로 이거였어요.

🙋‍♂️ 제네릭: "일반 큐는 '먼저 온 사람 먼저', 우선순위 큐는 '급한 사람 먼저'네요!"

이 일을 대신 해 주는 게 파이썬의 **heapq**예요. 위 응급실에서 응급도 숫자(5, 1, 3)를 넣는 것이나, 맨 위 코드에서 그냥 숫자(5, 2, 8, 1)를 넣는 것이나 똑같아요. heapq는 항상 가장 작은 값을 맨 위로 올려 두거든요.

🔍 코드 한 줄씩 뜯어보기

이제 맨 위에서 본 완성 코드를 한 줄씩 볼게요.

① 도구 가져오기

import heapq

heapq는 파이썬에 기본으로 들어 있는 우선순위 큐(최소 힙) 도구예요. import 한 줄만 쓰면 바로 쓸 수 있어요.

② 빈 힙 만들기

heap = []

힙은 그냥 리스트로 시작해요. 비어 있는 리스트 하나를 만들어 두면, 여기에 값을 넣고 꺼낼 거예요.

③ 값 넣기 — heappush

heapq.heappush(heap, 5)   # 5 삽입
heapq.heappush(heap, 2)
heapq.heappush(heap, 8)
heapq.heappush(heap, 1)
print(heap)               # [1, 2, 8, 5]

heappush(heap, 값)은 힙에 값을 넣는 함수예요. 신기한 건, 넣을 때마다 heapq가 가장 작은 값을 맨 앞(heap[0])으로 끌어올려 둔다는 거예요.

💡 출력이 [1, 2, 8, 5]라서 "왜 완전히 정렬이 안 됐지?" 싶을 수 있어요. 힙은 맨 앞이 항상 최솟값이라는 약속만 지켜요. 나머지 순서는 정렬돼 있지 않아도 괜찮아요. 우리가 필요한 건 "다음에 꺼낼 가장 작은 값"뿐이니까요.

④ 값 꺼내기 — heappop

print(heapq.heappop(heap))  # 1
print(heapq.heappop(heap))  # 2
print(heapq.heappop(heap))  # 5
print(heapq.heappop(heap))  # 8

heappop(heap)은 힙에서 그 시점의 가장 작은 값을 꺼내요. 하나 꺼내면 heapq가 남은 값들 중에서 다시 가장 작은 값을 맨 앞으로 올려 두죠. 그래서 계속 꺼내면 1 → 2 → 5 → 8 작은 순서대로 나와요.

⑤ 전체가 어떻게 굴러가는지

넣고 꺼내는 과정을 따라가 볼게요. ([ ] 안 맨 앞이 항상 다음에 꺼낼 최솟값이에요.)

push 5  → [5]
push 2  → [2, 5]
push 8  → [2, 5, 8]
push 1  → [1, 2, 8, 5]      맨 앞 = 1

pop → 1 꺼냄 → 남은 것 중 최솟값 2가 앞으로
pop → 2 꺼냄 → 다음 최솟값 5가 앞으로
pop → 5 꺼냄 → 마지막 8
pop → 8 꺼냄 → 힙이 비었어요

🙋‍♀️ 람다: "넣을 때 막 넣어도 꺼낼 땐 항상 가장 작은 게 먼저 나오네요. 응급실에서 급한 사람부터 부르는 거랑 똑같아요!"

✍️ 직접 완성해보기

이제 빈칸을 채워 직접 완성해봐요. 위에서 본 그대로예요.

import heapq

heap = []
heapq.___(heap, 5)          # 삽입 (heappush)
heapq.heappush(heap, 2)
heapq.heappush(heap, 8)
heapq.heappush(heap, 1)
print(heap)                 # [1, 2, 8, 5]
print(heapq.___(heap))      # 최솟값 꺼내기 (heappop) → 1
print(heapq.heappop(heap))  # 2
print(heapq.heappop(heap))  # 5
print(heapq.heappop(heap))  # 8

🐬 돌핀쌤: "막히면 위 '코드 한 줄씩 뜯어보기'로 다시 올라가서 확인해요. 다 채웠으면 맨 위 🎯 완성 코드와 비교해보세요. 정답을 외우는 게 아니라 왜 그런지 떠올리는 게 진짜 공부예요."

📌 오늘 배운 것

개념	설명
우선순위 큐	넣은 순서가 아니라 우선순위 순서(작은 값 먼저)로 꺼내는 자료구조
heapq	파이썬에 기본으로 들어 있는 우선순위 큐(최소 힙) 도구
heappush	`heapq.heappush(heap, 값)` — 힙에 값 넣기
heappop	`heapq.heappop(heap)` — 항상 가장 작은 값 꺼내기
heap[0]	힙의 맨 앞은 항상 최솟값(나머지는 정렬 안 돼 있어도 됨)

🐬 돌핀쌤: "heappush로 넣고, heappop으로 가장 급한 것부터 꺼낸다! 이 두 박자만 알면 우선순위 큐는 끝이에요. 잘했어요! 👏"

▸ 더 해보기 — 여기서부터는 선택!

여기까지가 오늘의 필수 내용이에요. 아래는 여유 있을 때 도전하는 내용이고, 예제 문제로 직접 풀어볼 수 있어요. 외울 필요는 없어요. 전부 오늘 배운 heappush/heappop 위에 살을 조금 더 붙인 것뿐이에요.

(우선순위, 값) 튜플 넣기 — 숫자만이 아니라 (1, "심정지")처럼 이름까지 같이 넣고 싶을 때예요. 힙은 튜플의 첫 번째 값(우선순위) 으로 비교해 줘요. → 예제로 연습
우선순위가 같을 때 — 우선순위가 같으면 두 번째 값으로 비교돼요. 도착한 순서대로 꺼내고 싶으면 (우선순위, 순서번호, 값)처럼 순서번호를 끼워 넣어요. → 예제로 연습
가장 작은/큰 N개 뽑기 — heapq.nsmallest(3, 리스트), heapq.nlargest(3, 리스트)로 전체 정렬 없이 상위/하위 N개만 빠르게 구해요. key=lambda 로 비교 기준도 바꿀 수 있어요. → 예제로 연습
최대 힙 만들기(음수 트릭) — heapq는 최소 힙만 있어요. 가장 큰 것을 먼저 꺼내려면 값에 음수(-) 를 붙여 넣고, 꺼낼 때 다시 음수로 뒤집어요. → 예제로 연습
응급실 시스템 만들기 — 지금까지 배운 걸 모아 환자 접수/치료를 처리하는 작은 클래스로 만들어 볼 수 있어요. → 예제로 연습

자주 하는 실수 세 가지

우선순위 없이 문자열만 넣기 — 문자열도 힙에 들어가지만 사전 순으로 정렬돼요. 의미 있는 순서가 필요하면 꼭 (우선순위, 값) 튜플을 쓰세요.
최대 힙에서 음수 뒤집기 깜빡 — 음수 트릭을 썼으면 꺼낼 때 -heapq.heappop(heap)처럼 다시 뒤집어야 원래 값이 나와요.
빈 힙에서 heappop — 비어 있는 힙에서 꺼내면 에러가 나요. if heap: 로 비었는지 먼저 확인하세요.

19 — 우선순위 큐(Priority Queue)

📃 해결할 문제

💻 예제 입력 1

🖨️ 예제 출력 1