플로이드-워셜
-
[프로그래머스] 합승 택시 요금(JavaScript)Problem-Solving/Problem 2022. 5. 18. 14:16
🍀 목차 문제 설계 구현(JavaScript) 최종 코드 훔쳐보기 문제 https://programmers.co.kr/learn/courses/30/lessons/72413 코딩테스트 연습 - 합승 택시 요금 6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] 82 7 3 4 1 [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]] 14 6 4 5 6 [[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4 programmers.co.kr 설계 사실 ..
-
[최단경로] 플로이드-워셜(Floyd-Warshall) 알고리즘Problem-Solving/Algorithm 2022. 5. 11. 15:18
🍀 목차 플로이드-워셜 알고리즘 같은 목적을 가진 알고리즘 기본 이해 구현(JavaScript) 그냥 다익스트라를 정점만큼 돌리면 안 되나요? 시간 복잡도 플로이드-워셜 알고리즘 가중 그래프에서 간선 가중치의 합이 최소가 되는 경로를 찾는 최단 경로를 찾기 위한 알고리즘 중 하나. 한 번 실행하여 모든 정점 - 모든 정점 간의 최단 경로를 구할 수 있는 알고리즘. 다이나믹 프로그래밍(DP)을 바탕으로 하고 있다. 음의 사이클이 없는 그래프라면 음의 가중치를 가졌을 때도 사용 가능. (음의 사이클의 존재를 판단할 수 있음.) 같은 목적을 가진 알고리즘 다익스트라 알고리즘 게시글에 정리해놓았다. 기본 이해 모든 정점과 모든 정점 간의 최단 거리를 구해야 하므로 2차원 배열을 생성, 갱신해 나간다. 단계별로 ..
