우선순위 큐(Priority Queue)와 코딩 테스트 활용법

1. 우선순위 큐(Priority Queue)란?

우선순위 큐는 가장 높은(또는 낮은) 우선순위를 가진 요소를 빠르게 꺼낼 수 있는 자료구조입니다.
일반적인 큐(First In, First Out)와 달리, 삽입 순서가 아닌 우선순위에 따라 요소를 처리합니다.

1.1 특징

1. 자동 정렬:
   • 요소가 삽입될 때, 우선순위를 기준으로 내부적으로 정렬됩니다.
2. 효율적인 접근:
   • 우선순위가 가장 높은 요소를 꺼내는 작업은 O(log N)의 시간 복잡도를 가집니다.
3. 활용 목적:
   • 우선순위가 중요한 작업을 빠르게 처리하는 데 사용됩니다. 예: 다익스트라 알고리즘, 작업 스케줄링 등.

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

파이썬에서는 우선순위 큐를 heapq 모듈을 이용해 구현합니다.
heapq는 최소 힙(min-heap) 기반으로 작동하며, 기본적으로 가장 작은 값이 먼저 나옵니다.

2.1 기본 사용법

from heapq import heappush, heappop

# 힙 생성
heap = []

# 요소 삽입
heappush(heap, 10)  # 10 삽입
heappush(heap, 5)   # 5 삽입
heappush(heap, 20)  # 20 삽입

# 최소값 꺼내기
print(heappop(heap))  # 출력: 5
print(heappop(heap))  # 출력: 10
print(heappop(heap))  # 출력: 20

2.2 최대 힙 구현

heapq는 기본적으로 최소 힙이므로, 최대 힙을 구현하려면 음수 값을 사용합니다.

from heapq import heappush, heappop

# 최대 힙 생성
heap = []

# 요소 삽입
heappush(heap, -10)  # 10 삽입 (음수화)
heappush(heap, -5)   # 5 삽입
heappush(heap, -20)  # 20 삽입

# 최대값 꺼내기
print(-heappop(heap))  # 출력: 20
print(-heappop(heap))  # 출력: 10
print(-heappop(heap))  # 출력: 5

3. 우선순위 큐의 활용 예시

우선순위 큐는 코딩 테스트에서 다음과 같은 문제를 해결할 때 자주 사용됩니다:

3.1 다익스트라 알고리즘

• 목적: 가중치가 있는 그래프에서 최단 경로를 구함.
• 우선순위 큐의 역할:
  • 현재 노드에서 비용이 가장 적은 경로를 먼저 처리.
  • 최소 힙을 이용해 가장 작은 비용을 가진 노드를 빠르게 꺼냄.

예제:

import heapq

def dijkstra(graph, start):
    n = len(graph)
    distances = [float('inf')] * n
    distances[start] = 0
    heap = [(0, start)]  # (비용, 노드)

    while heap:
        current_distance, current_node = heapq.heappop(heap)

        # 이미 처리된 노드라면 무시
        if current_distance > distances[current_node]:
            continue

        # 인접 노드 확인
        for neighbor, weight in graph[current_node]:
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(heap, (distance, neighbor))

    return distances

# 테스트용 그래프
graph = [
    [(1, 2), (2, 4)],  # 0번 노드에서 (1번 노드, 거리 2), (2번 노드, 거리 4)
    [(2, 1), (3, 7)],
    [(3, 3)],
    []
]

print(dijkstra(graph, 0))  # 출력: [0, 2, 3, 6]

3.2 작업 스케줄링

• 목적: 제한된 시간 안에 최대 작업을 처리하거나, 특정 작업의 우선순위를 조정.
• 우선순위 큐의 역할:
  • 각 작업의 우선순위를 기준으로 작업을 정렬하여 처리.

3.3 K번째 최소값/최대값 찾기

• 목적: 정렬 없이 배열에서 K번째로 작은 값 또는 큰 값을 찾기.
• 우선순위 큐의 역할:
  • 최대 힙 또는 최소 힙을 이용하여 빠르게 값을 추출.

예제:

from heapq import heappush, heappop

def find_kth_smallest(nums, k):
    heap = []
    for num in nums:
        heappush(heap, num)
    for _ in range(k - 1):
        heappop(heap)
    return heappop(heap)

nums = [7, 10, 4, 3, 20, 15]
k = 3
print(find_kth_smallest(nums, k))  # 출력: 7

4. 우선순위 큐의 시간 복잡도

1. 삽입: O(log⁡N)
   • 힙의 높이에 비례하여 삽입 작업 수행.
2. 삭제(추출): O(log⁡N)
   • 최소값/최대값을 꺼내면서 힙의 재구성을 수행.
3. 탐색: O(1)
   • 최소값 또는 최대값을 찾는 작업은 힙의 루트 노드에서 수행.

5. 우선순위 큐 사용 시 주의할 점

1. 최대 힙과 최소 힙 구분:
   • 기본적으로 heapq는 최소 힙을 제공합니다. 최대 힙이 필요하면 음수 값을 사용하는 방식으로 구현하세요.
2. 문제 요구 사항 확인:
   • 우선순위 큐가 가장 크거나 작은 값을 빠르게 꺼내는 문제에서만 적합합니다.
   • 일반적인 정렬 문제에는 sorted를 사용하는 것이 더 간단할 수 있습니다.
3. 데이터 구조 선택:
   • 데이터를 모두 정렬한 후 사용하는 문제에는 heapq가 비효율적일 수 있으므로, 문제의 성격에 맞는 자료구조를 선택하세요.

6. 정리

• 우선순위 큐는 최소값 또는 최대값을 빠르게 추출해야 하는 문제에서 강력한 도구입니다.
• 파이썬에서는 heapq를 사용하여 간단히 구현할 수 있습니다.
• 코딩 테스트에서는 주로 다익스트라 알고리즘, K번째 값 찾기, 작업 스케줄링 등의 문제에서 활용됩니다.
• 항상 문제의 요구 사항과 성능을 고려해 우선순위 큐를 활용하세요.