[Python] 알고리즘 개념11 퀴즈 - 우선순위 큐와 힙

 

 

📌 퀴즈 개요

다음 퀴즈를 통해 우선순위 큐(Priority Queue)와 힙(Heap) 개념을 정확히 이해하고 있는지 확인해 보세요! 😊

---

 

 

🧩 1. 개념 이해 문제

 

(1) 우선순위 큐(Priority Queue)의 특징으로 옳지 않은 것은?

1. 높은 우선순위를 가진 요소가 먼저 처리된다.
2. 일반적인 큐(Queue)와 다르게 삽입 순서가 중요하다.
3. 힙(Heap)을 사용하여 구현할 수 있다.
4. 모든 경우에서 항상 O(1)의 성능을 보장한다.

 

(2) 최소 힙(Min Heap)과 최대 힙(Max Heap)에 대한 설명으로 옳지 않은 것은?

1. 최소 힙의 루트 노드는 항상 가장 작은 값이다.
2. 최대 힙의 루트 노드는 항상 가장 큰 값이다.
3. 최소 힙에서 요소를 삽입할 때 O(n)의 시간이 걸린다.
4. Python의 heapq 모듈은 기본적으로 최소 힙을 제공한다.

---

 

 

🧩 2. 실전 문제

 

(3) 다음 코드의 실행 결과는?

import heapq
pq = []
heapq.heappush(pq, (2, 'B'))
heapq.heappush(pq, (1, 'A'))
heapq.heappush(pq, (3, 'C'))
print(heapq.heappop(pq))

1. (3, 'C')
2. (1, 'A')
3. (2, 'B')
4. (None, None)

 

(4) 다음 코드가 실행될 경우 출력될 결과는?

import heapq
max_heap = []
heapq.heappush(max_heap, -10)
heapq.heappush(max_heap, -5)
heapq.heappush(max_heap, -15)
print(-heapq.heappop(max_heap))

1. 5
2. 10
3. 15
4. -15

---

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

🏆 정답 및 해설

(1) 정답: 4
✅ 우선순위 큐는 일반적으로 O(log n) 시간복잡도를 가지며, 항상 O(1) 성능을 보장하지 않습니다.

(2) 정답: 3
✅ 최소 힙에서 요소를 삽입할 때 O(log n)의 시간이 걸립니다. O(n)이 아님에 주의하세요.

(3) 정답: 2
✅ heappop()은 우선순위가 가장 높은 요소를 제거하므로 (1, 'A')가 출력됩니다.

(4) 정답: 3
✅ 최대 힙은 Python의 heapq를 음수로 변환하여 사용하므로, -15가 가장 작은 값으로 저장되며, 이를 다시 양수로 변환하면 15가 출력됩니다.