0. 최단 경로최단 경로간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중에 간선의 가중치의 합이 최소인 경로하나의 시작 정점에서 끝 정점까지의 최단 경로다익스트라(Dijkstra) 알고리즘음의 가중치를 허용하지 않음벨만-포드(Bellman-Ford) 알고리즘음의 가중치 허용모든 정점들에 대한 최단 경로플로이드-워셜(Floyd-Warshall) 알고리즘이번에는 이 중에서 다익스트라( Dijkstra) 알고리즘을 알아본다.1. 다익스트라(Dijkstra) 알고리즘시작 정점에서 다른 모든 정점으로의 최단 경로를 구하는 알고리즘이다.시작 정점에서의 거리가 최소인 정점을 선택해 나가면서 최단 경로를 구하는 방식이다.그리디 기법을 사용한 알고리즘으로 정점 중심 그래프로 표현한다.프림(Prim) 알고리즘과 ..

0. 탐욕 알고리즘이란?탐욕 알고리즘은 최적해를 구하는 데 사용되는 근시안적인 방법이다.일반적으로, 머리 속에 떠오르는 생각을 검증 없이 바로 구현하면 Greedy 접근이 된다.각 선택 시점에서 이루어지는 결정은 그 순간에는 최적이지만, 그 선택이 모인 최종적인 해답이 최적이라는 보장은 없다.1. 배낭 짐싸기(Knapsack)배낭에 담을 수 있는 물건의 총 무게(W)가 정해져 있다.이 때, 배낭이 수용할 수 있는 무게를 초과하지 않으면서, 값이 최대가 되는 물건을 담는 경우, 그리디 알고리즘을  생각해볼 수 있다.1-1. 0-1 Knapsak배낭에 물건을 통째로 담아야 하는 문제 ➡ 물건을 쪼갤 수 없는 경우이 방식은 그리디 알고리즘을 적용하기 어렵다. 아래에는 총무게가 30kg인 배낭에 0-1Knaps..