알고리즘
1.Union & Find 알고리즘
서로 중복되지 않는 원소들로 나눠진 부분집합들, 즉 서로소 집합 자료구조인 Disjoint Set을 표현하는 알고리즘이다.Union Find 알고리즘은 Union과 Find라는 2가지 연산으로 이루어진다.Find(a, b) : a가 어떤 집합에 포함되어 있는지 찾는 연
2.크루스칼(Kruskal) 알고리즘
그래프 내에서 모든 정점들을 가장 적은 비용으로 연결하는 알고리즘이다. 즉, 최소 신장 트리를 구하는 알고리즘이다.그렇다면 최소 신장 트리는 무엇일까?최소 신장 트리를 알기 전에 신장 트리에 대해서 알아야한다.신장 트리그래프에서 모든 정점을 포함한다.정점 간 서로가 연
3.프림(Prim) 알고리즘
최소 신장 트리(MST)을 구현하기 위해 사용되는 알고리즘으로 시작 정점에서부터 정점을 하나씩 추가하며 트리를 확장하는 알고리즘이다.이 때 연결은 시작 정점으로부터 방문되지 않은 정들의 가중치 중에서 작은 값들만 찾아 탐색한다.(항상 최적의 해를 찾아서 감)임의의 정점
4.다익스트라(Dijkstra) 알고리즘
다익스트라 알고리즘은 그래프의 특정 정점에서 갈 수 있는 모든 정점들까지의 최단 경로를 구하는 알고리즘이다.매번 최단 경로의 정점을 선택해 탐색을 반복한다.그래프에서 최소 비용을 구하는 알고리즘은 다익스트라 알고리즘 외에 벨만-포드 알고리즘, 프로이드 워샬 알고리즘이
5.벨만-포드 알고리즘
그래프의 한 정점에서 다른 정점까지 가는 최단거리를 구하는 알고리즘이다.이전 시간에 다뤄봤던 다익스트라 알고리즘과 매우 비슷하지만 음의 간선이 존재해도 최단 경로를 찾을 수 있는 알고리즘이다.이전에 배웠던 최단 경로 알고리즘을 정리해보자.가중치가 없을 때(=동일할 떄)