[Python] heaqp 라이브러리를 이용한 우선순위 큐

heapq 라이브러리에 대해서 공부하기 전에 우선 heap에 대해 간략히 정리하자면, heap은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진트리를 기반으로 한 자료구조이다.

최소 힙은 가장 부모 노드의 최솟값을 가지고, 자식 노드로 갈수록 값이 커지는 특성이 있다. 힙 자료구조의 장점은 힙 자체로 정렬이 되며 값을 추가, 삭제할 때도 정렬이 유지된다는 장점이 있다. 

싸피교육때 힙 자료구조를 배우고 파이썬으로 구현은 해보았지만, heap을 이용하여 다양한 문제를 풀어보지는 못하여 heap을 꼭 알아야 하나?라는 생각에 공부를 미루고 있었는데, 다익스트라와 힙을 활용한 알고리즘 풀이 방식이 플로이드-와샬 알고리즘이 풀어내지 못한 문제를 거뜬히 풀어내는 것을 보고 힙도 공부할 필요가 있구나 싶어 공부하게 되었다.

싸피교육과정에서는 heap의 활용보다는 파이썬을 이용하여 heap자체를 구현해내는 것에 집중했었던 것 같아, 이번에는 heqpq라이브러리를 활용하여 heap을 어떻게 활용할 수 있는지 공부해보려고 한다.

우선 파이썬의 heqpq는 일반적인 heap와 다른 두가지의 특징이 있다. 파이썬의 heapq는 0의 인덱스부터 값을  가지고, 기본값으로 최소 힙을 가진다는 점이다. 이 두 가지 특징을 알아두고. heapq라이브러리를 활용하면 될 것 같다. (최대 힙을 구현하고 싶다면 -1을 곱한 상태로 만들면 된다.)

1. 힙 자료구조 만들기

• 빈 리스트([])를 이용하기
• heapq.heapify()를 사용하여 이미 저장된 리스트를 힙으로 바꾸기

heapify

2. 추가 / 삭제

• heapq.heappush(heap, item) : 힙의 특성을 유지하며, item 값을 heap으로 푸시한다.
• heapq.heappop(heap) : 가장 작은값 (최상단 노드)의 값을 팝 하고 반환한다. (일반적인 pop과 같이, 비어있다면 에러가 발생한다)
• heapq.heappush(heap, item) : item을 푸시한 후 가장 작은 값을 반환한다
• heapq.heapreplace(heap, item) : 가장 작은값을 팝, 반환 후 item을 푸시한다 

 

heapq 라이브러리를 통해 비교적 간편하게 힙 자료구조를 완성할 수 있다. 사실 여기 까지는 내가 배운 거랑 큰 차이가 없는데( 물론 그때는 지금보다 훨씬 어려웠던 것 같다.) 내가 조금 더 공부해보고 싶은 부분은 이것을 어떻게 활용하는지이다.

힙을 활용한 우선순위큐를 통해 다양한 알고리즘을 구현할 수 있겠지만, 우선은 다익스트라와 함께 사용할 수 있을 것이다.

내가 이해한 다익스트라 알고리즘은 각 목적지의 가는 비용을 최대로 해놓고, 그 비용이 더 적어질 때에만 그 목적지에 도달하고, 최신화하며 결국에는 각 목적지에 도달하는 최소비용을 구하는 알고리즘이다. 여기서 우선순위 큐를 활용한다면, 비용이 작은 경로부터 나오게 됨으로써, 비용이 클 때는 최신화하지 않는 다익스트라의 장점이 극대화될 수 있다는 점이다.

하나의 예시코드를 본다면,  이 코드는 백준 운동(1956)을 다익스트라와 우선순위 큐를 활용하여 푼 문제이다. 알고리즘을 설명하는 공간이 아니기 때문에 짧게 문제 설명을 하자면, 한 마을에서 출발하여 자신의 마을로 돌아올 때 가장 적은 비용으로 돌아오는 경우의 비용을 출력하는 문제이다.

문제 설명만 보자면 다익스트라보다는 플로이드-와샬알고리즘이 더 맞아 보이지만(다익스트라는 한 점에서 목적지까지 최소비용, 플로이드-와샬은 모든 점에서 모든 점까지 최소비용을 구하는 알고리즘이기 때문) 백준의 악랄한 시간제한은 파이썬으로 플로이드-와샬을 활용하여 통과할 수 없다.

하지만, 다익스트라와 우선순위큐를 활용하여 모든 점에서 다익스트라를 구현하여 가장 먼저 자기 자신에게 돌아온 경우를 출력한다면 정답을 찾을 수 있다. 말로만 했을 때는 다익스트라를 200개나 되는 모든 점에서 돌려야 되기 때문에 시간이 오래 걸릴 것 같지만 우선순위 큐와 합쳐진다면 플로이드-와샬보다 더 좋은 성능으로 문제를 해결할 수 있다.

우선순위 큐가 항상 현재까지 비용이 가장적은(정답일 가능성이 가장 높은) 경우를 뽑아내주기 때문에, 가장 먼저 사이클이 완성된 경우가 정답이 되기 때문이다.

플로이드-와샬알고리즘은 모든 점(자기 자신을 포함한) 최단거리를 구하고, 자기 자신을 방문한 결과 중 최솟값을 또 찾아서 정답으로 내야 하는 반면, 우선순위 큐를 활용한 다익스트라는 가장 먼저 사이클을 완성한 경우가 정답이기 때문에 성능적으로 더 좋게 되는 것이다.

우선순위 큐와, 다익스트라, 플로이드-와샬 알고리즘 모두 개념만 알고 있는 정도이지 아직 내 것이 되기에는 연습이 많이 필요한 것 같다. 교수님의 말씀대로 기출보다는 아직 알고리즘 유형에 대해 연습할 필요가 있을 것 같다.

 

자료출처 : 파이썬 공식문서 https://docs.python.org/3/library/heapq.html

heapq — Heap queue algorithm — Python 3.10.4 documentation

문제출처 : 백준  https://www.acmicpc.net/problem/1956

1956번: 운동