쾌락없는 책임 (공부)/알고리즘 공부
-
길찾기 알고리즘(3) - 벨만-포드 알고리즘쾌락없는 책임 (공부)/알고리즘 공부 2021. 6. 23. 22:30
벨만-포드 알고리즘 벨만 포드 알고리즘은 이전에 작성한 다익스트라 알고리즘, 플로이드-와샬 알고리즘과 더불어 자주 소개되는 길찾기 알고리즘입니다. 저 두개의 알고리즘보다 아주 뛰어난 성능을 가지는 알고리즘은 아니지만 아래 표와 같이 특징에 따라 분류된 알고리즘이라고 볼 수 있습니다. 다익스트라 플로이드-와샬 벨만-포드 빠르다 한 노드에서 다른 노드들 까지 거리를 구함 음의 가중치가 있으면 도달 불가 느리다 모든 노드 to 모든 노드의 거리를 구함 사건의 전후관계 파악에도 사용 다익스트라보다 느리다 음의 가중치가 있을때 사이클을 판단 벨만-포드 알고리즘을 배우는 큰 이유는 '음의 가중치'를 판별해내기 위함입니다. 만약 A->B->C->A의 경로를 지나면 음수의 가중치가 얻어진다고 하면, 기존 알고리즘은 이..
-
길찾기 알고리즘(2) - 다익스트라 알고리즘쾌락없는 책임 (공부)/알고리즘 공부 2021. 6. 17. 20:59
다익스트라 알고리즘 다익스트라 알고리즘은 최단거리를 구하는 알고리즘중 가장 대표적인 알고리즘으로 아래와 같은 조건에서 사용하면 좋습니다. - 간선간 음의 가중치가 없을때 - 시작지점이 한개의 정점으로 정해졌을 때 (시작점이 여러개라면 다익스트라를 여러번 돌려 해결이 가능합니다) 다익스트라 알고리즘은 '가장 빠른 길'을 찾는 알고리즘으로 간선간 음의 값을 가지는 길은 없다고 생각합니다. 또한 플로이드-와샬보다 속도는 빠르지만 시작지점 1개에 대해서만 빠른 길을 찾는 알고리즘입니다. 조금 풀어쓴 다익스트라 알고리즘 1. 시작점 start, 도착점 finish, 각 경로와 가중치가 주어지게 됩니다. - 입력을 전부 받아오면 다익스트라를 위한 배열을 아래 표처럼 INF로 초기화해줍니다. 1 2 3 4 5 INF..
-
길찾기 알고리즘(1) - 플로이드-와샬 알고리즘쾌락없는 책임 (공부)/알고리즘 공부 2021. 5. 29. 12:01
플로이드-와샬 알고리즘 플로이도-와샬 알고리즘의 기본 이론은 '중간에 경유지를 거쳐가는게 빠르다면 그 값으로 업데이트' 해주는 것입니다. 또한 이전의 다익스트라 알고리즘과의 차이라고 하면 다익스트라 알고리즘은 [ 시작지점 1개 to 여러 목적지 ] 를 구하는 알고리즘이라 모든 경로를 구할 수 없습니다. 하지만 플로이드-와샬 알고리즘의 경우 모든노드 to 모든 노드의 경로값을 구할 수 있다는 장점이 있습니다. 구현을 하게 되면 for문이 3개가 있어 O(n^3)의 시간 복잡도를 가지게 되고 경로를 저장할 2차원 배열이 필요하기 때문에 n^2만큼의 공간 복잡도가 필요하게 됩니다. 말로 풀어쓰는 플로이드-와샬 알고리즘 A B C A - 5 15 B 4 - 5 C 1 20 - A에서 B, C로 가는 비용이 5,..