아래 글은 나동빈 님의 "이것이 취업을 위한 코딩 테스트다 with 파이썬"을 참고하여 작성하였습니다.
대표 문제
우선순위 큐(Priority Queue)
스택(Stack)은 가장 나중에 삽입된 데이터를 가장 먼저 삭제하고, 큐(Queue)는 가장 먼저 삽입된 데이터를 가장 먼저 삭제한다. 우선순위 큐(Priority Queue)는 말 그대로 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 큐이다. 따라서 우선순위 큐는 데이터를 우선순위에 따라 처리하고 싶을 때 사용한다. 예를 들어 [[다익스트라 알고리즘]]에서 비용이 가장 작은 간선을 찾기 위해 사용된다.
대부분의 프로그래밍 언어에서는 우선순위 큐 라이브러리를 지원하기 때문에 일반적인 코딩 테스트 환경에서 직접 힙 자료구조부터 작성해서 우선순위 큐를 구현할 필요는 없다. 파이썬에서는 우선순위 큐가 필요할 때 PriorityQueue 혹은 heapq를 사용할 수 있는데, 이 두 라이브버리 모두 우선순위 큐 기능을 지원한다. 다만, PriorityQueue 보다는 일반적으로 heapq 가 더 빠르다.
또한 파이썬 라이브러리에서는 기본적으로 최소 힙(Min Heap) 구조를 이용하므로, 다른 언어 라이브러리와 헷갈리면 안된다. 언어마다 라이브러리의 자료구조가 조금씩 다르기 때문이다.
우선순위 큐의 구현 방식
일반적으로 우선순위 큐를 구현할 때는 힙 자료구조를 사용한다. 그러나 사실 우선순위 큐를 구현하는 방법은 다양하다. 데이터의 개수가 N개일 때, 리스트를 이용해서 우선순위 큐를 구현하기 위해서는 삭제할 때마다 모든 원소를 확인하고 우선순위가 가장 높은 것을 탐색해야 하므로, 최악의 경우 O(N)의 시간이 소요된다. O(N)의 연산을 N번 반복하므로 리스트로 우선순위 큐를 수행할 때의 시간 복잡도는 O(N^2)가 된다.
| 우선순위 큐 구현 방식 | 삽입 시간 | 삭제 시간 |
|---|---|---|
| 리스트 | O(1) | O(N) |
| 힙(Heap) | O(logN) | O(logN) |
그러나 힙 자료구조에서 삽입할 때는 O(logN)의 연산을 N번 반복하므로 O(NlogN)이고 삭제할 때도 마찬가지로 O(NlogN)이다. 따라서 전체 연산 횟수는 대략 2NlogN이므로, 빅오 표기법에 따라 전체 시간 복잡도는 O(NlogN)이 된다. 결국 리스트보다 힙을 이용하는 것이 모든 원소를 저장한 뒤에 우선순위에 맞게 빠르게 뽑아낼 수 있으므로, 힙은 우선순위 큐를 구현하는 데 가장 많이 사용된다.
힙 구현
class Heapq:
def __init__(self, n):
self.heapq = [None] + [0] * n
self.length = 0
def print(self):
print(self.heapq[1:self.length+1])
def heapify(self, left, right):
parent = left
temp = self.heapq[parent]
while parent < right//2+1:
cl = parent*2
cr = cl+1
child = cr if cr <= right and self.heapq[cr] > self.heapq[cl] else cl
if temp >= self.heapq[child]:
break
self.heapq[parent] = self.heapq[child]
parent = child
self.heapq[parent] = temp
def heappush(self, item):
self.length += 1
self.heapq[self.length] = item
child = self.length
temp = self.heapq[child]
while child//2 > 0:
parent = child // 2
if temp <= self.heapq[parent]:
break
self.heapq[child] = self.heapq[parent]
child = parent
self.heapq[child] = temp
def heappop(self):
if self.length == 0:
return 0
root = self.heapq[1]
self.heapq[1] = self.heapq[self.length]
self.length -= 1
if self.length > 0:
self.heapify(1, self.length)
return root힙 정렬 소스코드를 보고 아예 클래스로 한 번 구현해봤는데, 작동은 잘 되는데 속도가 현저히 느리다. heapq를 쓰면 통과하는 코드가 구현 힙으로 제출하면 시간초과가 난다. 어디에 불필요한 연산이 있는 것이겠지. 한 번 heapq 모듈을 뜯어서 어떤 로직으로 돌아가는지 살펴봐야겠다.
