우선순위 큐 ( Priority Queue )

안녕하세요 hp입니다 :)

오늘은 저번에 배운 큐 자료구조의 연장선인 우선순위 큐에 대해서 배워보도록 하겠습니다.

📚 개념

우선순위 큐는 데이터를 정렬된 상태로 저장하기 위해서 사용하는 것입니다.

큐의 개념을 생각해 보면 큐는 일반적으로 선입선출(FIFO) 특성을 가졌지만, 우선순위 큐 같은 경우에는 데이터 추가는 어떤 순서로 해도 상관이 없지만 제거될 때는 우선순위에 따라 제거됩니다.

즉, 내부적으로 데이터를 정렬된 상태로 보관하는 특징이 있고 구체적으로는 heapq 모듈을 통해 구현되어 있습니다.

💡 우선순위큐 메소드

• que.put()
  우선순위 큐에 원소를 추가합니다.

• que.get()
  우선순위 큐에서 원소를 삭제하고 값을 반환합니다.

PriorityQueue 클래스의 put()과 get() 메소드는 O(log n)의 시간복잡도를 가집니다.

from queue import PriorityQueue

que = PriorityQueue()

que.put(1)
que.put(2)
que.put(3)

print(que.get()) # 1
print(que.get()) # 2
print(que.get()) # 3

정수형태로 값이 설정되면 값이 작은 순서대로 삭제된다.

• 원소삽입 - 튜플형태 (우선순위 , 값)

que.put((1,'hello'))
que.put((2,'world'))

튜플형태로 우선순위를 설정해준 경우에는 우선순위 순서대로 삭제된다.

위와 같이 PriorityQueue에 대해서 공부해 봤는데요. 사실 파이썬에서 우선순위 큐를 구현하는 방법은 PriorityQueue 말고 위에 잠깐 나왔던 heap을 이용해서도 구현할 수 있습니다.

특히 heapq를 이용해서 구현할때는 PriorityQueue보다 더욱 빠르게 동작하기 때문에 코딩테스트를 준비할때 자주 사용하는것 같습니다.

heapq는 다음 포스팅으로 준비해서 찾아뵙겠습니다.

끝까지 읽어주셔서 감사합니다. 😁

🎯 문제풀이

문제 풀이는 heapq에서 추천해 드리겠습니다.