[python] 백준 1927 : 최소 힙 (실버 2)

https://www.acmicpc.net/problem/1927

해당 문제를 풀기 위해서는 우선순위 큐와 힙에 대해서 알아야 한다. 이를 위해 chat gpt 에게 물어보았다.

우선순위 큐 (Priority Queue)

우선순위 큐는 각 요소에 우선순위를 부여하여, 우선순위가 높은 요소가 먼저 처리되는 자료 구조입니다. 일반적인 큐(FIFO)와 달리, 요소는 우선순위에 따라 나열되고 처리됩니다. 우선순위 큐의 구현에는 다양한 방법이 있지만, 가장 일반적으로 사용하는 방법 중 하나는 **힙(Heap)**을 사용하는 것입니다.

힙 (Heap)

힙은 완전 이진 트리의 형태를 가지며, 부모 노드의 값이 자식 노드의 값보다 항상 크거나 작도록 하는 특성을 갖습니다. 힙은 크게 두 종류로 나뉩니다:

1. 최대 힙(Max Heap): 부모 노드의 값이 자식 노드의 값보다 항상 크거나 같다. 루트 노드는 가장 큰 값을 가집니다.
2. 최소 힙(Min Heap): 부모 노드의 값이 자식 노드의 값보다 항상 작거나 같다. 루트 노드는 가장 작은 값을 가집니다.

힙은 우선순위 큐를 구현하는 데 매우 적합합니다. 힙을 사용하면 삽입과 삭제 연산이 평균적으로 O(log n) 시간에 수행될 수 있기 때문입니다.

Python에서 우선순위 큐와 힙

Python에서는 heapq 모듈을 사용하여 최소 힙 기반의 우선순위 큐를 쉽게 구현할 수 있습니다.

최소 힙 예제

python

코드 복사

import heapq # 빈 힙 생성 heap = [] # 힙에 요소 추가 heapq.heappush(heap, 3) heapq.heappush(heap, 1) heapq.heappush(heap, 4) heapq.heappush(heap, 1) heapq.heappush(heap, 5) heapq.heappush(heap, 9) # 힙에서 요소 제거 print(heapq.heappop(heap)) # 1 print(heapq.heappop(heap)) # 1 print(heapq.heappop(heap)) # 3

최대 힙 예제

최대 힙을 구현하기 위해서는 heapq 모듈의 최소 힙 기능을 활용하여 값을 음수로 변환하여 처리하는 방법을 사용할 수 있습니다.

python

코드 복사

import heapq # 빈 힙 생성 max_heap = [] # 힙에 요소 추가 (음수로 변환하여 추가) heapq.heappush(max_heap, -3) heapq.heappush(max_heap, -1) heapq.heappush(max_heap, -4) heapq.heappush(max_heap, -1) heapq.heappush(max_heap, -5) heapq.heappush(max_heap, -9) # 힙에서 요소 제거 (음수로 변환하여 원래 값 복원) print(-heapq.heappop(max_heap)) # 9 print(-heapq.heappop(max_heap)) # 5 print(-heapq.heappop(max_heap)) # 4

우선순위 큐 사용 예제

아래는 heapq 모듈을 사용하여 우선순위 큐를 구현하고 사용하는 예제입니다.

python

코드 복사

import heapq class PriorityQueue: def __init__(self): self.heap = [] def push(self, item, priority): heapq.heappush(self.heap, (priority, item)) def pop(self): return heapq.heappop(self.heap)[1] def is_empty(self): return len(self.heap) == 0 pq = PriorityQueue() pq.push('task1', 2) pq.push('task2', 1) pq.push('task3', 3) while not pq.is_empty(): print(pq.pop())

정리

• 우선순위 큐: 각 요소에 우선순위를 부여하여 우선순위가 높은 요소를 먼저 처리하는 자료 구조.
• 힙: 부모 노드와 자식 노드 간의 관계를 유지하는 완전 이진 트리. 최대 힙과 최소 힙이 있으며, 우선순위 큐를 구현하는 데 사용됨.
• Python의 heapq 모듈: 최소 힙을 기본으로 제공하며, 최대 힙은 값을 음수로 변환하여 사용. heappush와 heappop 함수를 사용하여 힙에 요소를 추가하고 제거함.

import heapq
import sys
input = sys.stdin.readline

heap = list()

n = int(input().strip())

for _ in range(n):
    x = int(input().rstrip())
    if x == 0:
        if len(heap) == 0:
            print(0)
        else:
            print(heapq.heappop(heap))
    else:
        heapq.heappush(heap,x)

heapq 함수만 안다면 쉬운 문제이다.