Oneulog

개요 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산 음의 간선이 없을 때 정상적으로 동작 그리디 알고리즘으로 분류된다. -> 매상황에서 비용이 가장 적은 노드를 선택해 임의의 과정을 반복 동작 과정 출발 노드 설정 최단 거리 테이블을 초기화 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신 위 과정에서 3과 4를 반복 알고리즘 동작 과정에서 최단 거리 테이블은 각 노드에 대한 현재까지의 최단 거리 정보를 가지고 있다. 처리 과정에서 더 짧은 경로를 찾으면 '이제부터는 이 경로가 제일 짧은 경로야'라고 갱신한다. 동작 과정 살펴보기 [초기 상태] 그래프를 준비하고 출발 노드를 설정한다. 노드 번호 ..

우선 순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료 구조 힙(Heap) 우선 순위 큐를 구현하기 위해 사용하는 자료 구조 중 하나 최소 힙(Min Heap)과 최대 힙(Max Heap) 이 있다. 다익스트라 최단 경로 알고리즘을 포함해 다양한 알고리즘에서 사용된다. 우선순위 큐 구현 방식 삽입 시간 삭제 시간 리스트 O(1) O(N) 힙(Heap) O(logN) O(logN) 힙 라이브러리 사용 예제 : 최소 힙 import heapq # 오름차순 힙 정렬 def heapsort(iterable) : h = [] result = [] for value in iterable : # 모든 원소를 차례대로 힙에 삽입 heapq.heappush(h, value) for i in range(len(h)) :..