파이썬 알고리즘 인터뷰: 10장 우선순위큐, 데큐

Tae-Kyun Kim·2022년 4월 4일

원형 연결리스트 데큐

원형으로 구현하는 이유는 뒤쪽으로 요소를 채우다가 공간이 다 차게되면 tail과 head를 연결해 앞쪽의 빈 공간을 활용하려는 의도인대 연결 리스트는 애초에 빈 공간이라는 개념이 존재하지 않기 때문에 원형은 아무런 의미가 없다. 또한 데크의 연산은 맨 처음 과 맨 끝의 값을 추출할 뿐이며 맨 끝의 다음 값을 추출하는지 등의 연산은 존재하지 않기 때문에 서로 연결되어 있을 필요 또한 없다.

우선 순위 큐

요소를 삽입, 삭제할 때 정렬하는 $S(n)$ 의 시간만큼의 시간이 소요됨 (힙 정렬이라면 $n*log(n)$ )

최단 경로를 탐색하는 다익스트라Dijkstra 알고리즘 등 우선순위 큐는 다양한 분야에 활용되며 힙Heap 자료구조와도 관련이 깊다.

우선 순위 큐 풀이

파이썬 에서는 대부분의 우선순위 큐 풀이에 거의 항상 heapq모듈을 사용하므로 잘 파악해두 자. 왜 PriorityQueue 모듈을 사용하지 않고 heapq를 사용하는지는 277페이지에서 다시 설명한다

멀티스레드로 구현할 게 아니라면 PriorityQueue모듈은 사용할 필요가 없다 → GIL