[Codeforces] Dijkstra?
영어로 된 문제와 친해지기 위해 codeforces의 문제를 풀어봤다. 1900의 Difficulty를 가진 문제이며 다익스트라의 최단 경로 알고리즘을 이용해 실제 최단 경로를 출력하면 된다.
최근 포스트
[Baekjoon,1219] 오민식의 고민
도시를 방문할 때 마다 이익을 얻거나 손해를 본다. 여기서 출발 도시에서 시작하여 도착 도시로 왔을 때 얻을 수 있는 가장 큰 돈의 액수를 구해야 한다. 이 돈은 사이클을 형성하여 무한대로 얻을 수 있다. 여기서 손해를 최소화 하는 경로를 찾아야 한다고 생각할 수 있다. 즉,...
[Baekjoon,1956] 운동
모든 정점을 찾으며 자기 자신으로 돌아오는 경로가 존재하는 정점 중에서 경로의 최소값을 찾아야 한다. 여기서 플로이드 알고리즘을 활용할 수 있다.
[Baekjoon,10217] KCM Travel
이 문제의 그래프는 음수 가중치를 가진 간선이 없는 그래프이다. 그리고 단일 시작점에서 도착 점 까지의 최단거리를 구해야 하므로 다익스트라의 최단거리를 구하는 알고리즘을 이용하면 된다.
[Baekjoon,2749] 피보나치 수 3
이 문제를 해결하기 위한 방법이 두 가지 정도 있는데 하나는 피사노 주기를 이용하는 것이고, 다른 하나는 행렬을 이용하는 것이다. 여기서는 행렬을 이용한 방법만 소개하겠다.