Blog for Code

ASP는 모든 정점이 출발점이 되어 모든 정점에 대해 최단 경로를 구하는 것이다. 가장 쉬운 방법은 Dijkstra 알고리즘 또는 Bellman-Ford 알고리즘을 여러번 돌리는 것이다. 하지만 그렇게 하면, Dijkstra는 O(V^3 ), Bellman-Ford는 O(V^4 )번 걸리기 때문에 빠르지 않다. 그를 위해서 사용하는 더 빠른 알고리즘이 바로 Floyd-Warshall 알고리즘이다. Floyd-Warshall Algorithm Dijkstra 알고리즘을 모든 정점에서 수행한 것과 같은 알고리즘이지만 구현이 간단하고 negative-weight edge가 가능하다. - Negative edge를 허용한다 -> 그런 의미에서 Bellman-Ford 알고리즘과 비교한다. - negative-we..

Algorithm 2020. 5. 20. 23:22

Single Source Shortest Path에는 Bellman-Ford, DAG, Dijkstra's 알고리즘이 있다. - 1개의 source에 대해서 모든 vertex v로 가는 최단 경로를 찾는 문제이다. - d[v] = S[s,v] 를 의미한다. - 초기에 d[v]는 무한대인데 알고리즘을 돌면서 값이 줄어들어 shortest path의 값을 가지게 될 것이다. - π[v] = 바로 이전 vertex를 의미한다. - π를 이용해서 shortest-path tree를 만들 수 있다. 초기화 코드 모든 V에 있는 vertex까지의 거리를 무한대로 만들어주고 π를 NIL로 초기화해준다. 그리고 시작점인 s의 거리만 0으로 만들어준다. Relaxation 짧은 길 찾기. 더 짧은 길이 발견되면 바로 환..

Algorithm 2020. 5. 20. 17:45

최단 경로를 찾는 문제의 특징 : - Input : directed graph G = (V, E) with weight function w : E -> R - Source에서 Destination까지의 최소 가중치를 가지는 path를 찾는 문제이다. - p라는 경로의 가중치인 w(p) : p로 가는 길에 있는 모든 edge의 weight의 총합이다. - u부터 v까지의 shortest-path weight은 다음으로 구한다 : S(u,v) = 만약 u부터 v까지 가는 path가 존재하면 u에서 v까지는 path인 p 중의 mininum weight 없으면 무한대 Variants 최단거리를 찾는 문제는 크게 4종류로 나눌 수 있다. 1. Single-source shortest path : 하나의 S에서 ..

Algorithm 2020. 5. 20. 16:32

Prim's 알고리즘은 시작 vertice에서부터 출발해서 MST 집합을 단계적으로 확장해 나가는 방법이다. Prim's 알고리즘의 동작 - 시작 단계에서 시작 vertice만이 MST 집합에 포함된다. - 앞 단계에서 만들어진 MST 집합에 인접한 vertice들 중에서 최소 가중치를 가진 edge로 연결된 vertice를 선택하여 Tree를 확장해나간다. 즉, 가장 낮은 weight을 가장 먼저 선택한다. - 위의 과정을 tree가 (n-1)개의 edge를 가질 때까지 반복한다. 여기서는 priority queue Q를 사용한다. 하나의 tree만을 유지한다는 것이 kruskal과 다른 점이다. - Psuedocode Example of Prim's Algorithm Prim's Algorithm의 ..

Algorithm 2020. 5. 17. 21:16

Greedy algorithm - 결정을 해야 할 때마다 그 순간에 가장 좋다고 생각되는 것을 선택함으로써 최종적인 답을 도출한다. - greedy algorithm은 그 순간에 최적이지만, 전체적으로 최적이라는 보장이 없지만, Kruskal 알고리즘은 최적의 해답을 주는 것으로 증명되어있다. Kruskal Algorithm 동작 - 그래프의 edge들을 weight이 작은 것부터 순서대로 정렬한다. - 정렬된 edge 리스트에서 순서대로 사이클을 형성하지 않는 edge을 선택한다. 가장 낮은 weight를 먼저 선택한다. 사이클을 형성하는 edge를 제외한다. - 해당 edge를 현재의 MST의 집합에 추가한다. Example of Kruskal - 또 다른 그림 예제 다음 edge를 이미 선택된 ed..

Algorithm 2020. 5. 17. 21:00

연결된(connected), 무방향(undirected), 가중치(weighted) 한 그래프 중에 총 weight(edge의 weight의 합) 이 가장 최소인 spanning tree. connected graph에서 vertice가 n개 있을 때, edge가 n-1개 있어야 한다. => tree (cycle이 없다.) 총 weight의 합이 minimal한 것을 골라야 하기 때문에 Greedy algorithm 이다. 특징 1. 간선(edge)의 가중치의 합이 최소여야 한다. 2. n개의 정점(vertice)을 가지는 그래프에 대해 반드시 n-1개의 간선만을 사용해야 한다. 3. 사이클이 포함되어서는 안된다. MST는 여러개일 수 있다. Generic MST 어떤 A에 대하여 A U {(u,v)}도..

Algorithm 2020. 5. 17. 20:23

유명한 knapsack 문제 : 도둑이 박물관에서 물건을 훔치려고 할 때, single knapsack만 가지고 있는 도둑은 어떤 걸 훔쳐야 가장 큰 값을 훔칠 수 있을까? knapsack 문제에는 두가지 버전이 있다 1. 0-1 knapsack problem -> on&off, 담거나 담지 않거나 아이템을 쪼갤 수 없다. 이 문제는 Dynamic programming으로 풀 수 있다. Greedy는 불가. 2. Fractional knapsack problem -> 자를 수 있다고 생각 아이템을 쪼갤 수 있다. 이 문제는 Greedy, Dynamic programming 모두 가능하다. 1. Fractional knapsack problem fractional knapsack problem을 풀기 위해..

Algorithm 2020. 4. 30. 04:04

Greedy Algorithms 미리 정한 기준에 따라 그 때 그 때 가장 최적의 답을 선택하는 알고리즘 -> local optimum Coin change greedy 알고리즘의 활용 -> 최수 수의 동전으로 거스름돈 거슬러주기 예시 ) 74cents = 1(half-dollar)+2(dime)+4(penny) Activity-Selection Problem greedy 알고리즘의 활용 -> 놀이공원에서 가장 많은 놀이기구 탑승하기 activity(놀이기구)들은 각각 시작시간과 종료시간이 다르다. activity들의 정보를 보고 최대 몇개의 활동을 할 수 있을지 구한다. input : activity(a) 집합의 시작시간 (s), 종료시간(f) 17 bytes 를 필요로 한다. 하지만, 이것도 76bi..

Algorithm 2020. 4. 30. 02:58