개발자 모드

오늘은 최단 경로를 찾는 알고리즘 중 Dijkstra 알고리즘의 단점을 보완한 Bellman-Ford 알고리즘에 대해서 알아보겠습니다. Dijkstra 알고리즘의 단점 이전 포스팅에서 말한 Dijkstra 알고리즘의 단점을 찾아보셨나요?? 여기서 간단하게 다뤄봅시다. 0번 정점을 우선 방문했습니다. 그리고 1번 정점과 2번 정점에 대해서 값을 갱신해줍니다. 이제 1번 노드를 선택할 것입니다. 가중치도 같이 갱신해줍시다. 이제 2번 정점에 갈 차례입니다!! 2번 정점에서 값을 갱신해봅시다. 이렇게 모든 노드를 방문하고 알고리즘을 종료합니다. 이제 0번 노드로부터 각 노드의 최단거리를 알았습니다. 0에서 2로 가는 최단거리는 1 0에서 1로 가는 최단거리는 -2 뭔가 이상하지 않나요?? 사실 0에서 1로 가..

오늘은 하나의 그래프 내에 정점 A에서 정점 B까지 가는 최단 경로를 구하는 알고리즘 중 하나인 Dijkstra 알고리즘에 대해서 알아보겠스빈다. Dijkstra 알고리즘이란? 앞서 말씀드린 것처럼, Dijkstra 알고리즘은 그래프 내에서 어떤 정점으로부터 다른 정점으로 갈 때의 최단 경로를 구하는 알고리즘입니다. Dijkstra 알고리즘은 Dynamic Programming에 속하기도 하고 그리디 알고리즘에 속하기도 합니다. 더보기 Dynamic Programming(동적 계획법) DP는 하나의 큰 문제를 작은 문제로 나누어서, 작은 문제들에 대한 해답을 이용해 큰 문제를 해결하는 하나의 문제해결 패러다임입니다. 그리디 알고리즘을 이용해 A에서 B로가는 경로를 구했다고 해봅시다. 그러한 경로가 A ..