Dev On The Coffee Dev On The Coffee

# 벨만 포드 알고리즘 (Bellman-Ford Algorithm) 1. 벨만 포드 알고리즘 개요 벨만 포드 알고리즘(Bellman-Ford Algorithm)은 다익스트라 알고리즘과 거의 유사하다. 다만, 다익스트라 알고리즘과 달리 벨만 포드 알고리즘은 음의 값을 가지는 간선을 포함하여 알고리즘을 수행할 수 있다는 점이 큰 차이점이다. 위와 같이 5번 노드에서 2번 노드로 가는 간선의 비용이 -2인 그래프가 있다. 이 경우, 음의 간선이 존재하지만 얼마든지 오른쪽 테이블처럼 최소 비용을 계산해낼 수 있다. 그러나 음의 간선의 순환이 포함되어 있는 경우 최소 비용을 계산하는데 어려움이 생길 수 있다. 위 그래프는 음의 간선 비용이 -4인데 이 값이 상당히 작기 때문에 '3번 노드 -> 5번 노드 -> 2..

# 플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm) 1. 플로이드 워셜 알고리즘 개요 플로이드 워셜 알고리즘(Floyd-Warshall Algorithm)은 최단 경로를 구하는 또 하나의 대표적 알고리즘이다. 다만, 다익스트라 알고리즘이 '한 지점에서 다른 특정 지점까지의 최단 경로를 구하는 경우'에 사용한다면, 플로이드 워셜 알고리즘은 '모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구하는 경우'에 사용한다. 플로이드 워셜은 다익스트라처럼 단계별로 거쳐가는 노드를 기준으로 알고리즘을 수행하지만 매 단계마다 방문하지 않은 노드 중에 최단 거리를 갖는 노드를 찾는 과정이 없다. 그리고 2차원 테이블에 모든 노드의 최단 거리 정보를 저장하며, 이를 점화식을 통해 갱신한다는 점에..

# 최단 경로 알고리즘 (Shortest Path Algorithm) 최단 경로 알고리즘(Shortest Path Algorithm)이란 가장 짧은 경로를 찾는 알고리즘을 말한다. 최단 경로를 찾는 것은 여러가지 상황이 존재할 수 있는데, 대표적으로 (1) 한 지점에서 다른 한 지점까지의 최단 경로를 찾는 상황 (2) 한 지점에서 다른 모든 지점까지의 최단 경로를 찾는 상황 (3) 모든 지점에서 다른 모든 지점까지의 최단 경로를 찾는 상황을 생각해 볼 수 있다. 최단 경로 알고리즘은 일반적으로 그래프 자료구조를 기반으로 해 진행된다. 각 지점은 노드(Node)로 나타내고, 지점 사이를 연결하는 도로는 간선(Edge)으로 표현한다. 예를 들어, 노드는 도시, 마을, 국가 등으로, 간선은 도로, 통로 등으로..

# 그래프 탐색 하나의 자료구조로서 그래프(Graph)는 데이터와 데이터 사이의 관계를 잘 표현해주는 자료구조이다. 그래프는 기본적으로 데이터가 담기는 노드(Node)와 데이터 사이를 연결하는 간선(Edge)으로 이루어져있다. 노드는 정점(Vertex)이라고도 불린다. 그래프 탐색은 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 말하며, 간선으로 연결되어 있는 두 노드는 서로 '인접'해 있다고 한다. # DFS (Depth-First Search, 깊이 우선 탐색) DFS는 그래프의 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 특정한 경로로 먼저 최대한 깊숙이 탐색한 후, 다시 돌아와 다른 경로를 탐색한다. DFS는 스택이나 재귀함수를 활용해 구현하며, 기본 순서는 다음과 같다. 1. 탐색 시작 ..