이 포스팅에서 작성하는 내용은 이것이 취업을 위한 코딩테스트다 (나동빈 지음) 에서 발췌하였습니다. 1. 최단 경로(Shortest Path) - 말 그대로 가장 짧은 경로를 찾는 알고리즘. - 최단 경로 문제는 보통 그래프를 이용해 표현하며, 각 지점은 노드로 표현되고 지점 간 연결된 도로는 간선으로 표현 - 코딩테스트에서는 다익스트라 최단 경로와 플로이드 워셜 알고리즘 유형이 자주 등장 2. 다익스트라(Dijkstra) 최단 경로 알고리즘 - 그래프에서 여러 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구하는 알고리즘. - 이 알고리즘은 '음의 간선'(0보다 작은 값을 가지는 간선)이 없을 때 정상적으로 동작하며, 현실 세계 또한 음의 간선으로 표현되지 않아 GPS..
