Python 우선순위 큐(Priority Queue)란?
Python의 우선순위 큐(priority queue)는 데이터를 특정한 순서에 따라 저장하는 자료구조입니다. 일반적인 큐가 먼저 들어온 데이터를 먼저 처리한다면(FIFO), 우선순위 큐는 각 요소의 우선순위에 따라 처리 순서가 결정됩니다.
예를 들어, 리스트에서 가장 큰 값이 항상 앞에 오고 가장 작은 값이 마지막에 오도록 데이터를 정렬하고 싶은 경우가 있을 수 있습니다. 바로 이럴 때 우선순위 큐가 유용합니다. 우선순위 큐는 키 값 기준으로 오름차순 정렬된 상태를 유지하기 때문에, 큐에서 최솟값과 최댓값을 손쉽게 꺼낼 수 있습니다.
컴퓨터 과학에서 큐(queue)는 아이템을 선입선출(First-In, First-Out; FIFO) 방식으로 저장하는 자료구조입니다. 예를 들어 식당 주문 관리 앱을 만든다고 생각해 봅시다. 먼저 주문한 고객이 나중에 주문한 고객보다 먼저 음식을 받아야 하겠죠. 이런 경우 주문 순서를 추적하기 위해 큐를 사용하는 것이 자연스럽습니다.
Python에서 우선순위 큐를 구현하는 대표적인 방법은 다음 두 가지입니다.
- queue.PriorityQueue 클래스 사용
- heapq 모듈 사용
리스트(list) 구조로도 우선순위 큐를 만들 수는 있지만, 위 두 가지 방법보다 효율성이 크게 떨어집니다. 이 글에서는 리스트를 사용하지 말아야 하는 이유와 함께, 더 효율적인 두 가지 구현 방법을 예제 코드와 함께 살펴보겠습니다.
방법 1: queue.PriorityQueue 클래스
queue.PriorityQueue 클래스는 Python의 queue 라이브러리에 포함되어 있으며, 이를 사용해 우선순위 큐를 손쉽게 만들 수 있습니다. 이 클래스를 사용하려면 먼저 queue 라이브러리를 임포트해야 하며, 큐에서 아이템을 꺼낼 때는 get() 메서드를 사용합니다.
다음 import 문으로 PriorityQueue 클래스를 코드에 가져올 수 있습니다.
from queue import PriorityQueue
지역 콘서트 티켓 소지자를 위한 우선순위 큐를 만들어 보겠습니다.
from queue import PriorityQueue ticket_holders = PriorityQueue() ticket_holders.put((3, 'Paul')) ticket_holders.put((1, 'Miles')) ticket_holders.put((2, 'Dani')) while not ticket_holders.empty(): item = ticket_holders.get() print(item)
실행 결과는 다음과 같습니다.
(1, 'Miles') (2, 'Dani') (3, 'Paul')
코드를 하나씩 살펴보겠습니다. 먼저 queue 라이브러리에서 PriorityQueue 클래스를 임포트하고, ticket_holders라는 이름의 우선순위 큐를 초기화했습니다. 그다음 티켓 번호와 해당 티켓 소지자의 이름을 담은 튜플 세 개를 put() 메서드로 큐에 삽입했습니다.
마지막으로 while 반복문을 사용해 큐가 빌 때까지 모든 아이템을 순회하며, get() 메서드로 아이템을 하나씩 꺼내 출력했습니다. 실행 결과를 보면 티켓 번호가 가장 작은 순서대로, 즉 우선순위가 높은 순서대로 출력되는 것을 확인할 수 있습니다.
queue.PriorityQueue 방식은 효율적이고 사용법도 간단하기 때문에, 우선순위 큐가 필요할 때 가장 먼저 고려할 만한 선택지입니다.
방법 2: heapq 모듈
heapq 모듈 역시 Python에서 우선순위 큐를 구현할 수 있는 강력한 도구입니다. heapq 기반 자료구조는 우선순위 순서대로 아이템을 제거하며, 값이 가장 작은 아이템이 가장 높은 우선순위를 가집니다.
heapq 모듈을 사용하려면 먼저 다음과 같이 임포트해야 합니다.
import heapq
앞선 예제를 heapq 모듈로 다시 구현해 보겠습니다.
import heapq ticket_holders = [] heapq.heappush(ticket_holders, (3, 'Paul')) heapq.heappush(ticket_holders, (1, 'Miles')) heapq.heappush(ticket_holders, (2, 'Dani')) while ticket_holders: item = heapq.heappop(ticket_holders) print(item)
실행 결과:
(1, 'Miles') (2, 'Dani') (3, 'Paul')
먼저 heapq 라이브러리를 임포트한 뒤, 빈 리스트 ticket_holders를 초기화했습니다. 그다음 heappush() 메서드를 사용해 티켓 번호와 소지자 이름을 담은 튜플 세 개를 힙에 추가했습니다.
이후 while 반복문으로 큐의 모든 아이템을 순회하면서, heappop() 메서드로 힙 최상단의 아이템을 제거하고 콘솔에 출력했습니다. PriorityQueue와 마찬가지로 모든 아이템이 우선순위 순서대로 출력되는 것을 볼 수 있습니다.
리스트로 우선순위 큐를 만들면 안 되는 이유
엄밀히 말하면 Python 리스트 자료구조만으로도 우선순위 큐를 만들 수 있습니다. 리스트를 생성한 후 오름차순으로 정렬하면 되기 때문입니다. 하지만 이 방법은 비교적 비효율적입니다. 리스트의 아이템이 변경될 때마다 전체 리스트를 다시 정렬해야 하기 때문에 시간이 많이 소요됩니다.
저장할 값이 몇 개 되지 않는다면 일반 리스트로 충분할 수 있습니다. 하지만 더 큰 큐를 운영해야 한다면 리스트는 좋은 선택이 아닙니다.
참고용으로 리스트 기반 우선순위 큐의 예제를 살펴보겠습니다. 콘서트에 먼저 입장해야 할 티켓 소지자 순서를 저장하는 우선순위 큐를 만든다고 가정해 봅시다.
ticket_holders = [] ticket_holders.append((3, 'Paul')) ticket_holders.append((1, 'Miles')) ticket_holders.append((2, 'Dani')) ticket_holders.sort(reverse=True) while ticket_holders: item = ticket_holders.pop() print(item)
실행 결과:
(1, 'Miles') (2, 'Dani') (3, 'Paul')
이 코드에서는 ticket_holders라는 리스트를 만들고, 티켓 번호와 이름을 담은 튜플 세 개를 append()로 추가했습니다. 그다음 Python의 sort() 함수를 사용해 내림차순(reverse=True)으로 리스트를 정렬했습니다. 내림차순으로 정렬하는 이유는 pop()이 리스트의 끝에서부터 아이템을 제거하기 때문입니다.
마지막으로 while 반복문이 리스트의 모든 아이템을 순회하며 맨 뒤의 아이템을 하나씩 제거하고, 제거된 아이템을 콘솔에 출력합니다. 결과적으로 PriorityQueue나 heapq와 동일한 출력을 얻을 수 있지만, 매번 정렬해야 하는 부담이 있습니다.
결론
Python에서 우선순위 큐를 만드는 가장 일반적인 두 가지 방법은 heapq 모듈을 사용하는 것과 queue.PriorityQueue 클래스를 사용하는 것입니다. 기술적으로 리스트를 우선순위 큐처럼 활용할 수도 있지만, 이 방식은 데이터가 많아질수록 성능이 크게 저하되므로 확장성이 떨어집니다.
이번 튜토리얼에서는 실제 예제를 통해 Python에서 우선순위 큐를 만드는 방법을 살펴보았습니다. 이제 여러분도 전문가처럼 직접 우선순위 큐를 구현할 준비가 되셨습니다!