이 문제는 이것이 코딩테스트다 262페이지 문제이다. 최단 거리문제는 전부 똑같은 유형이다. 정답이 거의 동일하고 출력부분만 다른 경우가 많다. 이 문제는 입력의 값이 크기에 우선순위큐다익스트라 알고리즘을 이용하여야 한다. 다익스트라 구현 방식을 이해를 하여야 한다. 그리고 거리비용이 현재보다 커질 때는 가지치기(branch and bound)를 미리 해주어야 한다.는 것을 알아야 한다. https://yunzae.tistory.com/94 최단경로(다익스트라,플로이드워셜) 최단경로는 말 그대로 가장 짧은 경로를 찾는 알고리즘이다. 그래서 '길 찾기'문제라고도 불린다. 최단 경로 알고리즘 유형에서는 다양한 종류가 있는데, 상황에 맞는 효율적인 알고리즘이 정립 yunzae.tistory.com 아래는 나의..
최단거리
최단경로는 말 그대로 가장 짧은 경로를 찾는 알고리즘이다. 그래서 '길 찾기'문제라고도 불린다. 최단 경로 알고리즘 유형에서는 다양한 종류가 있는데, 상황에 맞는 효율적인 알고리즘이 정립되어 있다. 예를 들면 '한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우, 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 등의 다양한 사례가 존재한다. 상황에 맞는 알고리즘을 알고 있다면 문제를 좀 더 쉽게 풀 수 있다. 대표적으로 사용하는 최단 거리 알고리즘은 3가지인데 다익스트라(데이크스트라), 플로이드 워셜, 벨만 포드 알고리즘 이다. 이중 다익스트라와, 플로이드 워셜은 꼭 알아야 한다. 이 두가지에 대해서 설명을 하고 추후에 벨만 포드 알고리즘에 대해서 포스팅하겠다. 다익스..
