deulee의 개발 노트

지금까지 다룬 다익스트라나 벨만-포드 알고리즘들은 모두 한 시작점에서 다른 모든 정점까지의 거리를 구해 주었다. 하지만 한 개의 시작점이 아니라 모든 정점 쌍에 둘 사이의 최단 거리를 구해야 할 때도 있다. 이러한 문제를 해결하는 가장 쉬운 방법은 모든 정점으로부터 다익스트라 알고리즘을 적용하면 되는 것이다. 만약 음수 가중치가 있다면 벨만 포드 알고리즘을 사용하면 된다. 그러나 이것보다 좀 더 빠르고 간단한 방법이 있다. 그것은 이제 설명할 플로이드 워셜(Floyd-Warshall) 알고리즘이다. 플로이드 워셜 알고리즘은 모든 정점 쌍의 최단 거리를 저장하는 2차원 배열 dist[][]를 계산한다. 이 배열의 원소 dist[u][v]는 정점 u에서 v로 가는 최단 거리를 나타낸다. 정점의 경유점들 우선..

알고리즘/이론 2023. 6. 28. 23:09

벨만 포드 알고리즘이란? 벨만 포드 알고리즘(Bellman-Ford Algorithm)은 다익스트라 알고리즘과 마찬가지로 시작점을 정해주면 시작점 기준으로 다른 모든 정점으로의 최단 거리를 구해주는 알고리즘이다. 이때, 벨만 포드 알고리즘의 최대 특징은 다익스트라 알고리즘과는 달리 간선의 가중치가 음수일 때도 사용할 수 있다는 것이다. 벨만 포드 알고리즘의 구조 그럼 벨만 포드 알고리즘은 무엇이 다르기에 음수의 가중치가 있어도 최단경로를 구할 수 있는 것일까? 벨만 포드 알고리즘은 2중 for문을 이용하여 가능한 모든 경우를 전부 다 체크한다. 우선 최단 경로의 정의를 알아볼 필요가 있다. 최단 경로란 같은 정점을 두 번 지날 일이 없다는 것을 의미한다. 즉, 가능한 최단 경로의 간선 개수는 많아봐야 V..

알고리즘/이론 2023. 5. 23. 14:16

BFS는 가중치가 있는 간선이 있는 그래프에서는 최단 거리 알고리즘으로써 사용될 수 없다. 그 이유는 BFS는 방문한 순서대로 동작을 하게 되기 때문이다. 그렇기 때문에 다음과 같은 상황에서 전혀 사용할 수 없는 것이다. 시작점이 A라고 가정해보자. 시작점 A를 방문하게 되었을 때 BFS 알고리즘을 이용하게 된다면 (2, B)와 (12, C)를 '그냥 큐'에 넣게 될 것이다. 그리고 나서 D를 방문하게 되고 알고리즘은 종료를 하게 될 것이다. 이렇게 될 경우 BFS 알고리즘 입장에서 A에서 C까지의 최단 경로가 12가 되는 것이다. 실제로는 2 + 4 + 3 = 9 인데도 말이다. 즉, A에서 C까지의 최단 경로는 A to C가 아니라 A to B to D to C가 되는 것이다. 이러한 상황에서 BFS..

알고리즘/이론 2023. 5. 21. 20:20

다익스트라(Dijkstra) 알고리즘은 그래프 이론을 활용한 대표적인 최단 경로(Shortest Path)탐색 알고리즘이다. 이 알고리즘은 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 구할 수 있는 알고리즘이다. 하지만 이 때 음의 간선을 포함하고 있는 경우 이 알고리즘은 사용할 수 없다는 점을 기억하고 이 글을 읽어보도록 하자. 하지만 애초에 다익스트라(Dijkstra) 알고리즘 BFS(너비 우선 탐색)을 기반으로 만들어진 알고리즘이기 때문에 BFS와 유사한 점이 많이 있다. 하지만 BFS는 가중치가 있는 그래프, 즉 각 간선마다 비용이 정해져 있는 경우 사용할 수 없다. 그 이유는 너비 우선 탐색은 발견한 순서부터 탐색을 시작하기 때문이다. 이 이유는 다른 장에서 따로 설명하도록 하겠..

알고리즘/이론 2023. 5. 21. 20:12

우선 선형 시간안에 트리의 지름을 구하는 방법은 다음과 같다. 트리에서 임의의 정점 X를 정한다. 정점 X에서 가장 먼 정점 Y를 구한다. 정점 Y에서 가장 먼 정점 Z를 구한다. 즉, 트리의 지름은 정점 Y와 정점 Z 사이의 거리를 의미한다. 이를 증명하는 방법은 다음과 같다. 증명 만약 트리에서 정점 U와 정점 V를 연결하는 경로가 트리의 지름이라고 가정하자. 임의의 정점 X를 정하고, X에서 가장 먼 정점 Y를 찾았을 때, 아래와 같이 경우를 만들 수 있다. X가 U 혹은 V인경우 Y가 U 혹은 V인경우 X, Y, U, V가 서로 다른 경우 이 경우 1, 2번은 무조건 올바르게 작동할 수 밖에 없다. 그야 DFS 알고리즘에 의해서 당연히 성립될 수 밖에 없다. 그럼 문제는 3번의 경우이다. 3번의 ..

알고리즘/이론 2023. 5. 20. 18:33