춤추는 개발자

플로이드 와샬 - '모든 정점'으로부터 다른 '모든 정점'까지 이동하는 최단 경로를 구하는 알고리즘 - 다익스트라와의 차이점은 특정한 하나의 정점이 아닌 '모든 정점'이라는 것입니다. - 해당 알고리즘은 기본적으로 '특정 노드를 거쳐가 다른 노드로 이동'이라는 특징이 있습니다. (k - i - j) - 핵심 아이디어는 '거쳐가는 정점'을 기준으로 최단 거리를 구하는 것! www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net public static void cal..

벨만-포드 알고리즘 - 앞서 포스팅한 다익스트라와 유사한 최단경로 알고리즘입니다. - 다익스트라와의 차이점은 가중치가 음수가 포함된 상황에서도 적용 가능하다는 특징입니다. - 정점의 개수가 N이라면 시작 노드를 제외한 (N-1)회 반복문을 수행하여 최단 경로를 구할 수 있습니다. www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net public static void checkedTimeMachine() ..

다익스트라 - '최단 경로는 여러 개의 최단경로로 이루어졌다.' - 다이나믹 프로그래밍을 활용한 대표적인 최단 경로 탐색 알고리즘, 하나의 정점(Node)에서부터 다른 정점까지로 가는 최단 경로를 알 수 있습니다. (대신, 가중치가 음수인 경우 적용할 수 없습니다.) - 기본적으로 하나의 최단 경로를 구할 때, 이전까지 구한 최단 경로 정보를 그대로 활용한다는 특징이 있습니다. 다익스트라의 작동과정 1. 출발노드 선정 2. 출발노드를 기준으로 연결된 노드마다 최소 비용 저장 3. 방문하지 않은 노드 중 최소 비용의 노드 선택 4. 다른 노드로 이동할 경우, 최소 비용을 갱신하며 이동 5. 3~4번 반복 www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 ..