다익스트라2

• 

  벨만-포드(Belman-Ford) 알고리즘 & 다익스트라(Dijkstra) 알고리즘 & A* 알고리즘 이렇게 3개의 알고리즘을 하나로 묶은 이유는, 모두 최단 경로를 찾는 알고리즘이기 때문입니다. 최단 경로 문제- 시작점, 끝점이 정해져있음.- 가중 그래프가 주어졌을 때, 최단 경로를 구해야 합니다.  벨만-포드(Belman-Ford) 알고리즘- 음수 비용이 있을 경우에도 사용 가능합니다.- 첫 위치를 0로, 나머지 위치를 ∞로 설정해 놓는다. ex) A에서 G로 갈때, 최단 경로를 구하시오.1) A를 0으로,  나머지를 ∞로 설정합니다.2) 간선(A-B)을 골라 거리를 구합니다. (B : 9, A: 0)2) 또 다른 간선(A-C)을 구해 최단 거리를 구합니다. (C: 2)3) 또 다른 간선(B-C)를 구해 최단 거리를 구합니다. (B : 8)4) 또 다른 간선(B-E), (B-D)을 구해 최단 거리를 .. CS 지식/자료구조_알고리즘 2025. 1. 14.

• 

  힙(Heap)과 이진탐색트리(Binary Search Tree) 힙(Heap)- 트리구조 중 하나로 우선순위 큐를 구현할 때 사용됩니다. (다익스트라에서도 사용됨.)- 우선순위 큐의 특징 : 데이터를 자유롭게 추가 가능, 꺼낼 때는 가장 작은 데이터를 꺼냅니다. - 힙은 노드들로 구성되어 있습니다.각각의 노드들은 부모와 자식으로 이루어져 있고, 부모는 최대 2개의 자식 노드를 가질 수 있습니다.- 부모 노드의 데이터가 자식 노드의 데이터보다 항상 작아야합니다. ex) 새로운 수를 힙에 추가하는 예시.1) 새로운 숫자를 힙의 가장 끝에 추가합니다.2) 만약 부모 노드가 존재한다면, 부모 노드와 데이터를 비교 후 숫자가 더 작다면 그 둘의 위치를 바꿔줍니다.3) 계속 그렇게 해서, 더 이상 부모보다 작지 않을 경우, 정렬은 종료됩니다. ex) 숫자를 하나 꺼낼때의 예시... CS 지식/자료구조_알고리즘 2025. 1. 9.