반응형 플로이드3 [백준/C++] 플로이드 2 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 플로이드 워셜 알고리즘 문제에 경로를 역추적 하는 게 추가된 문제다.이전에 풀었던 플로이드문제" data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 모든 경로에 대해 구해야 하므로 플로이드 워셜 알고리즘을 이용하면 O(n^3)으로 구할 수 있다. 플로이드 워셜 알고리즘이란 쉽게 말해 몇 번의 경로를 거쳐서 가는게 최소 비용이 되는지 구하는 방법으로 n개의 노드가 있을 때, [i][j]로 가는 최소 경로를 구하는 방법은 그 사이에 포함 될 수 있는 모든 노드의 수 만큼 k를 반복하면 되.. 2024. 5. 14. [백준/C++] 운동 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 특정 도시에서 시작해 다시 돌아오는 사이클이 있는지 확인하고 있다면, 그 중 가장 비용이 적은 사이클을 출력하는 문제다. 사이클을 찾기 위해서는 결국 st 에서 st로 돌아오는 최소비용을 구해야 한다. 문제는 시작점이 하나만 주어진게 아니라 모든 도시가 시작점이 될 수 있다는 점이다. 그러므로 결국 모든 도시에 대해서 시작점으로 돌아오는지 탐색을 해야한다. 처음에는 priority queue를 사용한 다익스트라 알고리즘으로 풀려고 했으나, N개의 점에 대해 다익스트라 연산을 하면 시간복잡도가 O(V*Elog(V))가 된다. [(E < V*2) 이므로 log(V)로 표현 가능] 그러면 O(V^3log(V.. 2024. 4. 23. [백준/C++] 플로이드 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 특정 정점에서 다른 정점으로 갈 수 있는 최단거리를 구하는 문제다. 모든 정점의 경우를 구해야하기 때문에 플로이드 워셜 알고리즘으로 문제를 풀면 O(N^3)의 시간복잡도로 문제를 해결할 수 있다. 문제를 풀기전에 플로이드 워셜 알고리즘을 간단하게 정리하면, 정점 i에서 j로 가는 비용과 정점 i -> k -> j로 가는 비용을 비교해 최단 거리를 갱신하는 과정이다. 위의 과정을 3중 for문을 이용하면 모든 정점에서 다른 정점으로 가는 최소비용을 구할 수 있다. 여기서 중요한 점은 경유지 k가 for문의 가장 상위에 있어야 한다. 왜 가장 상위에 있어야 하는지 설명하기 전에, 지나갈 수 있는 경유지의 .. 2024. 4. 21. 이전 1 다음 반응형