우선순위 큐

[최단경로] 다익스트라 - Python

최단경로 알고리즘 그래프 상에서 가장 짧은 경로를 찾는 알고리즘 최단경로를 찾는 알고리즘으로는 다익스트라 알고리즘과 플로이드 워셜 알고리즘, 벨만포드 알고리즘이 있다 종류 한 지점에서 다른 특정 지점까지의 최단 경로 모든 지점에서 다른 모든 지점까지의 최단 경로 모두 구하기 등이있음 표현 방법 그래프로 표현하며 각 지점은 그래프에서 노드로 표현되고, 지점간 연결된 도로는 그래프에서 간선으로 표현됨 다익스트라 알고리즘 '단계마다 방문하지 않은 노드 중에서 가장 최단 거리가 짧은 노드'를 선택한 뒤에 그 노드를 거쳐가는 경우를 확인해 최단 거리를 갱신하는 방법 우선순위 큐를 이용해 소스코드를 작성해야 효율적이다 역할 : 한 지점에서 다른 모든 지점까지의 최단 경로를 계산합니다 음의간선(0보다 작은 값을 가지..

우선순위 큐와 heap - python

참고 | 이코테2021 | 우선순위 큐 우선순위 큐 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조 우선순위 큐는 데이터를 우선순위에 따라 처리하고 싶을 때 사용 ex) 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건부터꺼내서 확인해야 하는 경우 구현 방법 단순히 리스트 이용해 구현 가능 힙(heap)을 이용해 구현 가능 데이터가 N개일 때 구현 방식에 따른 시간복잡도 우선순위 큐 구현 방식 삽입 시간 삭제시간 리스트 O(1) O(N) 힙(Heap) O(logN) O(logN) 단순히 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업은 정렬과 동일(힙 정렬) 이 경우 시간 복잡도는 O(NlogN) 힙의 특징 힙은 완전 이진 트리 자료구조의 일종 힙에서는 항상 루트 노드를 제거한다 최소 힙(m..