파이썬의 우선순위 큐(Priority Queue) 이해하기

우선순위 큐(Priority Queue)는 큐의 한 종류로, 각 요소가 우선순위를 가지며, 이 우선순위에 따라 요소가 처리되는 자료구조입니다. 일반적인 큐가 FIFO(First-In-First-Out) 방식으로 동작하는 반면, 우선순위 큐는 가장 높은 우선순위를 가진 요소가 먼저 처리됩니다. 이번 글에서는 파이썬에서 우선순위 큐를 구현하는 방법과 활용 사례를 알아보겠습니다.

1. 우선순위 큐란?

우선순위 큐는 다음과 같은 특징을 가진 자료구조입니다:

• 우선순위 기반 처리: 각 요소는 우선순위를 가지며, 우선순위가 높은 요소가 먼저 처리됩니다.
• 힙(Heap)을 사용한 구현: 우선순위 큐는 힙을 사용하여 효율적으로 구현할 수 있습니다. 최소 힙(Min-Heap)을 사용하면, 항상 우선순위가 가장 높은(가장 작은) 요소를 빠르게 추출할 수 있습니다.

1.1. 우선순위 큐의 사용 사례

우선순위 큐는 다음과 같은 상황에서 유용하게 사용됩니다:

• 다익스트라 알고리즘: 그래프에서 최단 경로를 찾는 알고리즘으로, 우선순위 큐를 사용하여 가장 짧은 경로를 우선적으로 탐색합니다.
• 작업 스케줄링: 작업이 여러 개 있고, 각 작업이 우선순위를 가질 때, 우선순위가 높은 작업을 먼저 처리합니다.
• 이벤트 시뮬레이션: 여러 이벤트가 발생할 때, 우선순위 큐를 사용하여 가장 중요한 이벤트를 먼저 처리합니다.

2. 파이썬에서 우선순위 큐 구현하기

파이썬에서는 heapq 모듈을 사용하여 우선순위 큐를 쉽게 구현할 수 있습니다. heapq 모듈은 최소 힙을 기본으로 제공하며, 이를 통해 우선순위 큐를 효율적으로 다룰 수 있습니다.

2.1. heapq를 사용한 우선순위 큐 기본 구현

import heapq

# 빈 우선순위 큐 생성
priority_queue = []

# 요소 삽입 (우선순위, 값)
heapq.heappush(priority_queue, (1, "Task 1"))
heapq.heappush(priority_queue, (3, "Task 3"))
heapq.heappush(priority_queue, (2, "Task 2"))

# 우선순위가 가장 높은 요소 추출
highest_priority_task = heapq.heappop(priority_queue)
print("Highest priority task:", highest_priority_task)  # 출력: Highest priority task: (1, 'Task 1')

위 코드에서 heapq.heappush를 사용하여 우선순위와 함께 요소를 삽입하고, heapq.heappop을 사용하여 우선순위가 가장 높은 요소를 추출할 수 있습니다.

2.2. 튜플을 사용한 복합 우선순위 처리

우선순위가 동일한 경우, 값에 따라 우선순위를 정렬해야 할 때 튜플을 사용할 수 있습니다.

import heapq

# 빈 우선순위 큐 생성
priority_queue = []

# 우선순위가 같은 경우, 튜플의 두 번째 요소에 따라 정렬됨
heapq.heappush(priority_queue, (1, "Task 1"))
heapq.heappush(priority_queue, (1, "Task 2"))
heapq.heappush(priority_queue, (2, "Task 3"))

while priority_queue:
    task = heapq.heappop(priority_queue)
    print("Processing:", task)

위 코드에서 우선순위가 같은 경우, 튜플의 두 번째 요소가 사전순으로 정렬되어 처리됩니다.

2.3. 최대 힙을 사용한 우선순위 큐 구현

기본적으로 heapq는 최소 힙을 제공합니다. 최대 힙을 사용하려면 우선순위의 부호를 반대로 바꿔주면 됩니다.

import heapq

# 빈 우선순위 큐 생성
priority_queue = []

# 요소 삽입 (우선순위, 값) - 우선순위의 부호를 반대로 하여 최대 힙 구현
heapq.heappush(priority_queue, (-1, "Task 1"))
heapq.heappush(priority_queue, (-3, "Task 3"))
heapq.heappush(priority_queue, (-2, "Task 2"))

while priority_queue:
    task = heapq.heappop(priority_queue)
    print("Processing:", (-task[0], task[1]))

위 코드에서 우선순위의 부호를 반대로 하여 최대 힙을 구현했습니다. 따라서 우선순위가 가장 높은 요소가 먼저 처리됩니다.

2.4. PriorityQueue 클래스 사용하기

파이썬의 queue 모듈에서 제공하는 PriorityQueue 클래스를 사용하여 우선순위 큐를 구현할 수도 있습니다. PriorityQueue 클래스는 스레드 안전(Thread-safe)을 보장합니다.

from queue import PriorityQueue

# 우선순위 큐 생성
priority_queue = PriorityQueue()

# 요소 삽입 (우선순위, 값)
priority_queue.put((1, "Task 1"))
priority_queue.put((3, "Task 3"))
priority_queue.put((2, "Task 2"))

# 우선순위가 가장 높은 요소 추출
while not priority_queue.empty():
    task = priority_queue.get()
    print("Processing:", task)

위 코드에서는 PriorityQueue 클래스를 사용하여 우선순위 큐를 구현했습니다. 이 클래스는 heapq 모듈과 유사하게 동작하지만, 멀티스레딩 환경에서 안전하게 사용할 수 있습니다.

3. 우선순위 큐 활용 사례

우선순위 큐는 다양한 문제 해결에 사용됩니다. 대표적인 활용 사례는 다음과 같습니다:

3.1. 다익스트라 알고리즘

다익스트라 알고리즘은 그래프에서 최단 경로를 찾는 알고리즘으로, 우선순위 큐를 사용하여 효율적으로 구현할 수 있습니다.

import heapq

def dijkstra(graph, start):
    distances = {vertex: float('infinity') for vertex in graph}
    distances[start] = 0
    priority_queue = [(0, start)]

    while priority_queue:
        current_distance, current_vertex = heapq.heappop(priority_queue)

        if current_distance > distances[current_vertex]:
            continue

        for neighbor, weight in graph[current_vertex]:
            distance = current_distance + weight

            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))

    return distances

graph = {
    'A': [('B', 1), ('C', 4)],
    'B': [('A', 1), ('C', 2), ('D', 5)],
    'C': [('A', 4), ('B', 2), ('D', 1)],
    'D': [('B', 5), ('C', 1)],
}

distances = dijkstra(graph, 'A')
print(distances)  # 출력: {'A': 0, 'B': 1, 'C': 3, 'D': 4}

위 코드에서 우선순위 큐를 사용하여 다익스트라 알고리즘을 구현했습니다. 그래프에서 출발 노드 A로부터 다른 모든 노드까지의 최단 거리를 계산합니다.

3.2. 작업 스케줄링

우선순위 큐를 사용하여 작업의 우선순위에 따라 작업을 처리할 수 있습니다. 이는 운영체제의 작업 스케줄링이나 이벤트 처리에 유용합니다.

import heapq

tasks = [(1, 'Write code'), (4, 'Do laundry'), (2, 'Read book')]

# 힙을 사용한 우선순위 큐 생성
heapq.heapify(tasks)

# 우선순위가 높은 작업부터 처리
while tasks:
    priority, task = heapq.heappop(tasks)
    print(f"Processing task: {task} with priority {priority}")

위 코드에서 우선순위 큐를 사용하여 작업을 우선순위에 따라 처리합니다. 우선순위가 높은 작업이 먼저 실행됩니다.

결론

이번 글에서는 파이썬에서 우선순위 큐를 이해하고 구현하는 방법을 살펴보았습니다. 우선순위 큐는 다양한 알고리즘과 문제 해결에 매우 유용한 자료구조입니다. heapq 모듈을 사용하여 우선순위 큐를 쉽게 구현할 수 있으며, 다익스트라 알고리즘이나 작업 스케줄링과 같은 다양한 사례에 적용할

수 있습니다. 실습을 통해 우선순위 큐의 개념을 익히고, 이를 다양한 상황에서 활용해보세요.

---

이 글을 통해 파이썑의 우선순위 큐 개념과 구현 방법에 대해 이해하고, 이를 활용하는 방법을 익힐 수 있을 것입니다. 우선순위 큐를 적절히 활용하여 효율적인 알고리즘과 데이터 처리를 구현해 보세요!