본문 바로가기
반응형

2017/06/032

[알고리즘] 최단경로(Shortest Path Problem) - 2 최단경로(Shortest Path Problem) - 2 위의 그림은 Bellman-ford 알고리즘의 예이다.첫번째 라운드에서 모든 엣지들에 대해서 relax 한다.relax연산이 끝나면 초기 시작점과 인접한 엣지들의 ∂값이 세팅된다.이렇게 순차작으로 relax 연산을 실행한다.위 그림은 한가지 실행 가능한 예이며, 어떠한 엣지를 선택하느냐에 따라서 다른 순서를 가진다. 이 Bellman-ford는 시간 복잡도에서 그리 좋은 알고리즘은 아니다.위의 그림은 왜 Bellman-ford의 시간 복잡도가 비효율적인지 알려준다.Bellman-ford 의 최악의 상황이 표현되었고, d[v]가 한번 갱신될때 마다 우측의 노드들의 값이 바뀐다.이는 불필요한 계산이 증가한다는 것이고, 그에따른 오버 헤드도 증가한다. .. 2017. 6. 3.
[Backjoon] 11653번 문제 - 소인수분해 정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오. 풀이 우선 2개의 반복문을 사용한다.외부에 while은 입력 받은 수가 나눗셈 연산을 거듭하면서 마지막에 1로 수렴하는 것을 판단한다.for는 나눠지는 수를 찾기 위해 i가 2부터 증가하며 만약 입력 받은 값이 i로 나눠진다면 나눈후 i값을 출력한다. 123456789101112131415161718192021import java.util.Scanner; /** * Created by homr on 2017. 6. 3.. */public class Main { public static void main(String[] args){ Scanner sc = new Scanner(System.in); int num = sc.nextInt(); wh.. 2017. 6. 3.
반응형