우선순위 큐(Priority Queue)는 큐(Queue)나 스택(Stack)과 비슷한 축약 자료형이다.
일반적인 큐는 FIFO(First in-First Out) 구조이지만 우선순위 큐(Priority Queue)는 들어간 순서에 상관없이
우선순위가 높은 데이터가 먼저 나오는 구조이다.
파이썬에서는 heapq 또는 PriorityQueue 라이브러리를 사용해서 우선순위 큐를 구현할 수 있다.
import heapq
nums = [4, 1, 7, 3, 8, 5]
heap = []
for n in nums:
heapq.heappush(heap, n)
while heap:
print(heapq.heappop(heap))
heapq.heappush를 사용해서 우선순위 큐에 요소를 삽입하고, heapq.heappop을 사용해서 pop 할 수 있다.
heapq는 기본적으로 최소 힙이라서 값이 작은 (1, 3)부터 (3, 1), (10, 2)가 순서대로 pop 되는 것을 확인할 수 있다.
큰 것부터 pop 하고 싶다면 아래 코드와 같이 구현해주면 된다.
import heapq
nums = [4, 1, 7, 3, 8, 5]
heap = []
for n in nums:
heapq.heappush(heap, (-n, n))
while heap:
print(heapq.heappop(heap)[1], end=' ')
print()아래 코드는 PriorityQueue를 사용해서 구현한 우선순위 큐이다.
from queue import PriorityQueue
q = PriorityQueue(maxsize=4)
q.put(3)
q.put(7)
q.put(2)
q.put(9)
print(q.get(), end= ' ')
print(q.get(), end= ' ')
print(q.get(), end= ' ')
print(q.get(), end= ' ')우선순위 큐는 다익스트라 알고리즘이나, K번 째 최댓값을 찾을 때 등등에 사용할 수 있다.
아래는 대표적인 우선순위 큐 문제 풀이이다.
백준 11279번 최대 힙)
import heapq
import sys
input = sys.stdin.readline
N = int(input())
q = []
for _ in range(N):
n = int(input())
if n != 0:
heapq.heappush(q, -n)
else:
print(-heapq.heappop(q) if q else 0)백준 1927번 최소 힙)
import heapq
import sys
input = sys.stdin.readline
N = int(input())
q = []
for _ in range(N):
n = int(input())
if n != 0:
heapq.heappush(q, n)
else:
print(heapq.heappop(q) if q else 0)
백준 알고리즘 문제 풀이)
백준 알고리즘 11279번 최대 힙(python)
기본적인 우선순위 큐 문제이다. import heapq import sys input = sys.stdin.readline N = int(input()) q = [] for _ in range(N): n = int(input()) if n != 0: heapq.heappush(q, -n) else: print(-heapq.heap..
jinho-study.tistory.com
백준 알고리즘 1927번 최소 힙(python)
기본적인 우선순위 큐 문제이다. import heapq import sys input = sys.stdin.readline N = int(input()) q = [] for _ in range(N): n = int(input()) if n != 0: heapq.heappush(q, n) else: print(heapq.heappo..
jinho-study.tistory.com
백준 알고리즘 11286번 절댓값 힙(python)
기본적인 우선순위 큐 문제이다. import heapq import sys input = sys.stdin.readline N = int(input()) q = [] for _ in range(N): n = int(input()) if n != 0: heapq.heappush(q, (abs(n), n)) else: print(he..
jinho-study.tistory.com
백준 알고리즘 1655번 가운데를 말해요(python)
우선순위 큐를 사용해서 빠르게 중앙값을 찾아야 되는 문제이다. 우선순위 큐를 2개(최대 힙, 최소 힙) 사용한다는 점이 핵심이다. 왼쪽 우선순위 큐는 최대 힙으로 최댓값이 맨 처음에 오도록
jinho-study.tistory.com
백준 알고리즘 1417번 국회의원 선거(python)
기본적인 우선순위 큐 문제이다. 최대 힙으로 구현해주면 된다. import heapq N = int(input()) D = int(input()) q = [] for _ in range(N-1): n = int(input()) heapq.heappush(q, -n) res = 0 while q: n = -he..
jinho-study.tistory.com
백준 알고리즘 14235번 크리스마스 선물(python)
기본적인 우선순위 큐 문제이다. 파이썬에서 우선순위 큐는 heapq 라이브러리 또는 queue 라이브러리의 PriorityQueue를 사용하면 쉽게 구현할 수 있다. 나는 그냥 heapq 라이브러리를 사용해서 풀었다.
jinho-study.tistory.com
백준 알고리즘 15903번 카드 합체 놀이(python)
기본적인 우선순위 큐 문제이다. import heapq n, m = map(int, input().split()) q = list(map(int, input().split())) heapq.heapify(q) for _ in range(m): a = heapq.heappop(q) b = heapq.heappop(q) heapq.h..
jinho-study.tistory.com
백준 알고리즘 2075번 N번째 큰 수(python)
골드 5 난이도 치고는 매우 쉬운 우선순위 큐 문제이다. 최대 힙 우선순위 큐로 구현해서 N번째 pop결과를 출력해주는 식으로 풀어도 답은 맞지만 메모리 초과가 뜬다. heapq의 nlargest를 사용해서
jinho-study.tistory.com
백준 알고리즘 1715번 카드 정렬하기(python)
기본적인 우선순위 큐 문제이다. 이 문제도 골드 4 난이도 치고는 쉽다. 우선순위 큐에 남은 수가 2개 이하가 되기 전까지 제일 작은 두 값을 pop 해서 더하고, 그 합을 우선순위 큐에 추가하고 res
jinho-study.tistory.com
'Agorithm > 자료구조, 알고리즘 정리' 카테고리의 다른 글
| 플로이드-와샬(Floyd-Warshall) 알고리즘 (백준 문제 포함) (0) | 2021.03.22 |
|---|---|
| 다익스트라(Dijkstra) 알고리즘 (백준 문제 포함) (0) | 2021.03.22 |
| 퇴각검색(Backtracking) (백준 문제 포함) (0) | 2021.03.20 |
| 동적 계획법(Dynamic programming) (백준 문제 포함) (0) | 2021.03.17 |
| 너비 우선 탐색(breadth-first search, BFS) (백준 문제 포함) (0) | 2021.03.10 |