밤이 블로그

BOJ#2293 동전1 * 문제https://www.acmicpc.net/problem/2293 * 풀이정말 이해하기 쉽지 않은 문제였습니다.조금 더 완벽하게 이해한 후에 저의 풀이를 포스팅하도록 하겠습니다. 참고한 풀이 : http://blog.naver.com/occidere/220784778900import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; /** * BOJ#2293 동전1 * https://www.acmicpc.net/problem/2293 */ public class Main { // dp[i] : n가지 종류의 동전..

BOJ#1865 웜홀 * 문제https://www.acmicpc.net/problem/1865 * 풀이 벨만-포드 알고리즘을 활용하는 기본 문제입니다. 일단 기본적인 풀이 방법은 "BOJ#11657 타임머신" 문제와 같고,음수 간선 사이클이 존재하는지 확인만 하면 되는 문제입니다. 주의할 점 #1)도로에 방향이 없으므로,도로 정보를 입력 받을 때 양방향으로 생각해야 한다는 점입니다. -> 결국 Edge의 개수는 2 * M + W -> 코드 상 여러번 쓰이게 되므로, 실수하지 않게 따로 변수로 저장해둡시다. 주의할 점 #2)시작점이 주어지지 않았으므로, 시작점을 어느 곳으로 해야 할 지 결정해야 합니다. 음수 사이클은 웜홀이 연결된 지점에서만 존재 할 수 있으므로웜홀의 목적지들을 배열에 따로 저장하여, 이..

BOJ#11657 타임머신 * 문제https://www.acmicpc.net/problem/11657 * 풀이벨만-포드 알고리즘 문제입니다. → http://stack07142.tistory.com/79 알고리즘 설명은 위 링크를 참고하시면 됩니다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; /** * BOJ#11657 타임머신 * https://www.acmicpc.net/problem/11657 */ public class Main { static final int NONE = -1; static final int IN..

벨만-포드 알고리즘(Bellman-Ford algorithm) 최단 경로 알고리즘에서 대표적인 것으로는 1) 다익스트라 : 유향그래프, 한점 - 다수의 점, 음수 가중치 X2) 벨만-포드 : 유향그래프, 한점 - 다수의 점, 음수 가중치 O, 음수 사이클 X3) 플로이드-와샬 : 모든 점- 모든 점 여기서는 벨만-포드 알고리즘에 대해 알아보겠습니다. * 벨만-포드 알고리즘(Bellman-Ford algorithm) 벨만-포드 알고리즘은 가중 유향 그래프에서 최단 경로 문제를 푸는 알고리즘이다. 이때 변의 가중치는 음수일 수도 있다. 다익스트라 알고리즘은 벨먼-포드 알고리즘과 동일한 작업을 수행하고 실행 속도도 더 빠르다. 하지만 다익스트라 알고리즘은 가중치가 음수인 경우에는 처리할 수 없으므로, 이런 경..