반응형 분류 전체보기340 [알고리즘] 최단경로(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. [알고리즘] 최단경로(Shortest Path Problem) - 1 최단경로(Shortest Path Problem) - 1 이번시간에는 그래프 알고리즘 중에서 가장중요하고 유명한 최단 경로에 대해 알아보자최단 경로는 이름 그대로 가장 짧은 경로를 찾는 것이다.먼저 최단경로 문제에서는 가중치를 가진 그래프가 주어진다.사실 최단 경로에서는 방향/무방향이 무의미하다. 따라서 방향 그래프를 예시로 설명을 진행한다. 경로의 길이를 정의해야하는데, 길이는 그 경로상에 있는 모든 가중치들의 합이다.따라서 최단 경로는 U에서 V로가는 가장 짧은 길이를 말한다.그러므로 이렇게 U에서 V까지의 최단 경로를 ∂(U,V)라고 정의한다.최단 경로 문제의 목적은 ∂(U,V)를 구하는 것이다. 최단 경로의 문제의 유형에 따라 구분을 할수 있다.먼저 하나의 출발 노드로부터 모든 노드의 최단 경로를.. 2017. 6. 2. [알고리즘] 최소비용신장트리(Minimum Spanning Tree) - 4 최소비용신장트리(Minimum Spanning Tree) - 4 이번에는 두번째 MST인 프림의 알고리즘에 대해 알아보자프림의 알고리즘도 마찬가지로 안전한 엣지를 하나씩 추가함으로 완성되는데안전한 엣지를 찾는 방법이 크루스칼의 알고리즘과 다르다. 프림의 알고리즘에서는 먼저 출발점인 노드를 선택해야한다.그리고 그 출발점인 노드에서부터 점점 몸집을 키우기 시작한다.즉, 출발 노드에서 인접한 노드를 선택하고, 여기서 나가는 엣지를 하나 선택하고, 이를 반복한다.크루스칼에서는 떨어진 노드들을 선택했는데 프림의 알고리즘은 인접한 노드를 선택하는것이 차이점이다. 이 때, 어떤 엣지를 선택하느냐에 대한 방법을 알아봐야하는데,매 단계에서 트리에 포함되어진 노드와 포함되지 않은 노드 사이에 가중치가 가장 작은 엣지를 선.. 2017. 6. 2. 이전 1 ··· 29 30 31 32 33 34 35 ··· 85 다음 반응형
