TIL 5일차

오늘도 어김없이 solved.ac 클래스 올리기 

 

1865 문제를 통해서 벨만포드와 다익스트라 차이를 짚었다. 

 

다익스트라는 O(eloge) = O(elogv) 알고리즘의 최단거리 찾기 알고리즘이며, 방문한 정점은 체크하며 두번 방문하지 않도록 한다. 음수가중치가 있을 시에 문제가 발생할 수 있다. 

 

벨만포드는 O(ve)알고리즘의 최단거리 찾기 알고리즘으로 정점을 순서대로 선택한다. 모든 간선을 반복하며 릴렉스를 한다. n-1만에 최단거리를 구할 수 있으며 다음 n번째에서도 릴렉스가 발생할 시 음수 싸이클 존재를 알수있다.

 

클래스 4부터 문제를 많이 풀지 못하는 것 같다.

 

-----

 

오늘 해결한 백준 문제들

1629 곱셈 - 분할정복 - 다시 풀어 볼만한 문제

1753 최단거리 - 다익스트라

1786 찾기 - KMP

1865 웜홀 - 벨만포드 - INF 를 Integer.MAX_VALUE할시 릴렉스 도중 오버플로우를 생각하여 INF가 아닐 경우만 릴렉스를 하려하면 안된다. INF여도 음수 가중치에 의해서 릴렉스 될 가능성이 있다. 물론 오버플로우 가능성도 존재한다.