머직타드

그래프 자료구조에서 최단 경로, 최소 비용를 구해야 하는 알고리즘은 너비 우선 탐색(BFS), 다익스트라, 벨만-포드, 플로이드 워샬 이 있습니다. 1. 플로이드 와샬(Floyd-Warshall) 알고리즘이란? 플로이드 와샬은 그래프 자료구조에서 노드와 가중치가 있는 간선이 존재할 때 모든 정점간의 최소 비용을 구할 수 있는 그래프 탐색 알고리즘 입니다. 5개의 노드와 6개의 간선이 존재하는 그래프 예시를 들겠습니다. 여기서 간선의 방향은 단지 갈수 있냐, 없냐를 결정지을 뿐 중요하지 않습니다. BFS나 다익스트라 같은 탐색 기법은 특정 노드끼리의 최소 비용만 구하면 됩니다. 즉 탐색을 시작하는 시작 노드가 정해져 있는 경우에 해당됩니다. 하지만 플로이드 와샬은 모든 노드간의 최소 비용을 구할 수 있습니..

그래프 자료구조에서 최단 경로, 최소 비용를 구해야 하는 알고리즘은 너비 우선 탐색(BFS), 다익스트라, 벨만-포드, 플로이드 워샬 이 있습니다. 1. 다익스트라(Dijkstra) 알고리즘 이란? 그래프 자료구조에서 노드와 가중치가 있는 간선이 존재하고, 시작 노드에서 모든 노드까지의 최단 경로(최소 비용)를 구하는 알고리즘 입니다. 위 그래프를 예시로 보자면, 1번 노드를 시작해서 다른 모든 노드(2, 3, 4, 5)까지의 최단 경로를 구해야 합니다. 그리고 각 노드를 잇는 간선(방향 존재 유무는 중요하지 않습니다. 갈 수 있냐, 없냐 차이 이므로!)에는 가중치가 있습니다. 이 그래프에서 노드1을 시작으로 다익스트라 알고리즘을 적용해 다른 노드까지의 최단 경로를 구해 보겠습니다. 2. 다익스트라 적용..

1. 탐욕 알고리즘(Greedy Algorithm) 이란? Greedy: (형용사) 탐욕스러운, 욕심 많은 "매 선택에서 현재 가장 최적인 답"을 선택해 전체에서 최적의 결과를 도출하는 알고리즘 기법입니다. 순간마다 선택 가능한 경우의 수 중에서, 가장 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행합니다. 최적의 경로만을 찾아 탐색하게 되므로 모든 경로를 탐색할 필요가 없습니다. 이 때문에 속도가 매우 빠른 알고리즘으로 자주 사용될 수 있습니다. 하지만, 그 결과가 최적이라는 보장은 없습니다. 아래의 예시로 설명해 드리겠습니다. 위 그래프는 A에서 출발하여 최종 목적지인 E로 가는 경로를 선택하는 예시입니다. A에서 출발하여 다음 선택 가능한 B, C, D 중에 가장 가중치가 낮은 1인 간선을 골..