소피it블로그

자료 출처: https://youtu.be/acqm9mM1P6o 1. 플로이드 워셜 알고리즘 최단 경로 알고리즘으로, 모든 노드에서 다른 모든 노드까지의 최단 경로를 구하는 알고리즘 다익스트라 알고리즘의 경우 한 노드에서 다른 모든 노드까지의 최단 경로를 구하는 알고리즘인데 반해, 플로이드 워셜 알고리즘은 모든 노드에서 다른 모든 노드까지의 최단 경로를 구한다는 점이 차이점이다. 거쳐가는 노드를 기준으로 알고리즘을 수행하는 것은 다익스트라 알고리즘과 동일하나, 매 단계마다 방문하지 않은 노드 중 최단 거리를 갖는 노드를 찾는 과정이 필요 없다는 점이 다르다. 2차원 테이블에 최단 거리 정보를 저장한다. 다이나믹 프로그래밍 유형에 속하며, 삼중 반복문을 사용한다. 시간 복잡도는 O(N^3) 노드의 개수가 ..

자료 출처: https://youtu.be/acqm9mM1P6o 동빈북을 사두고 생각보다 어려워서 많이 못 봤는데, 이 강의 시리즈를 보다보니 이해가 쉽게 가고 재밌어서 대강 쭉 봤다. 요즘 블로그에 정리하는 내용들도 강의 요약본이나 마찬가지인데, 어려운 알고리즘들은 계속 읽어보며 완전히 이해가 될 때까지 못 넘기겠어서 하나하나 코멘트를 다는 중. 투머치이긴 하지만 내가 이해하기 위한 것이기 때문에 그냥 적으려 한다. 1. 최단 경로 알고리즘 개요 한 지점에서 다른 한 지점까지 한 지점에서 다른 모든 지점까지: 다익스트라 알고리즘 모든 지점에서 다른 모든 지점까지: 플로이드 워셜 알고리즘 이 때 각 지점은 노드로, 지점 간을 연결하는 도로는 간선으로 표현한다. 2. 다익스트라 최단 경로 알고리즘 특정 노..