helloahram

다익스트라를 공부하는데 코드 구현에서 heapq 가 나와서 정리한다 힙큐 heapq최대값과 최소값을 찾는 연산에 특화된 완전 이진 트리 우선순위 큐를 위해 만들어 자료 구조이다  최소힙 Min Heap 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작은 것최대힙 Max Heap 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 것 힙큐는 최소힙 자료 구조를 이용한다  heapq 메서드1. heapq.heapify(iterable)원래 있던 리스트를 힙으로 사용하기 위해 힙화 (heapify) 진행Heapify 의 디폴트 값은 최소힙이다import heapqheap2 = [5, 2, 1, 3, 8]heapq.heapify(heap2)print(heap2) # 결과 출력 [1, 2, 5, 3, 8..

다익스트라 Dijkstra최단 경로 Shortest Path 탐색 알고리즘 가중 방향 그래프 G = (V, E) 에서 모든 간선의 가중치가 음이 아닌 경우에 단일 출발점 최단 경로 문제를 푼다  다익스트라 특징1. 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 사용한다 2. 가중치가 음수인 경우는 적용이 될 수도 있고 안 될 수도 있다3. 무방향 그래프, 방향 그래프 모두 사용 가능하다  다익스트라 동작 과정1. 시작 정점 설정 - 시작 정점을 설정하고, 그 정점에서 다른 모든 정점으로 가는 최단 거리를 계산한다                 처음에는 시작 정점의 거리를 0으로, 나머지 모든 정점의 거리는 무한대로 설정2. 미방문 정점 중 최단 거리 선택 - 아직 방문하지 않은 ..

위상 정렬 Topology Sort순서가 정해져 있는 작업을 차례로 수행해야 할 때 그 순서를 결정해 주기 위해 사용하는 알고리즘 사이클이 없는 DAG 에만 적용이 가능하다  DAG Directed Acyclic Graph 방향이 있는, 비순환적인 그래프대학교의 선후수 과목에 비유할 수 있다전자회로 과목은 회로이론과 기초전자회로실험 과목을 이수해야 수강이 가능하다 여기에서 회로이론과 기초전자회로실험의 수강 순서는 중요하지 않다  진입 차수와 진출 차수위상 정렬 동작 과정을 보기 전에 진입 차수와 진출 차수에 대한 개념을 먼저 알아 두어야 한다 진입 차수 Indegree 는 노드로 들어오는 간선의 개수이고진출 차수 Outdegree 는 노드에서 나가는 간선의 개수이다 위상 정렬 동작 과정1. 진입 차수가..