All-Pairs Shortest Paths (APSP) 문제 정의앞서 소개했던 Single-Source Shortest-Paths (SSSP)는 단일 vertex에서의 최단 경로 가중치와 정점을 구했었다.이번엔 알아볼 APSP는 u에서 v로 가는 모든 정점 쌍 (u, v)를 찾는 방법이다. 방향이 있는 그래프 G(V, E)가 주어지면 edge의 가중치 함수를 실수 값으로 매핑하고, 해당 그래프를 행렬 W로 표현한다. 이와 같이 가중치 행렬 W가 주어지면최단 경로 거리 행렬 D와, 최단 경로 선행 정점 행렬 Π를 계산한다. APSP 문제 풀이 방법 저번에 배웠던 SSSP 알고리즘으로도 APSP 문제를 해결할 수 있다. single souce이니만큼 당연하겠지만..모든 정점을 출발점 source..
MST와 Shortest Paths의 차이 소개 https://guhonga.tistory.com/139 Minimum Spanning Tree (MST) 소개 - Kruskal, Prim’s algorithmMST 소개 및 특징Spanning Tree란, cycle을 갖지 않고 그래프 내의 모든 정점이 연결된 트리를 말한다.n개의 vertex가 있는 Spanning Tree라면 n-1 개의 edge가 있다. 그렇다면 Minimum Spanning Tree (MST) 가 의미하guhonga.tistory.com 앞에서 설명했던 MST 알고리즘은 그래프에서 모든 노드를 포함하면서, 사이클이 없고, 총 가중치의 합이 최소인 트리를 찾는 알고리즘이었다. 즉, 모든 노드를 연결하는 최소 비용의 트리를 찾는 알..
MST 소개 및 특징Spanning Tree란, cycle을 갖지 않고 그래프 내의 모든 정점이 연결된 트리를 말한다.n개의 vertex가 있는 Spanning Tree라면 n-1 개의 edge가 있다. 그렇다면 Minimum Spanning Tree (MST) 가 의미하는 것은모든 spanning tree에 대해 최소 가중치를 갖는 트리를 말한다. 방금 말한 spanning tree의 특징 외에 추가적으로 MST가 갖는 특징은위 예시를 통해 확인할 수 있듯이, 그 모양이 유일하지 않다는 것이다. MST 만들기MST를 만들기 위해 우리는 edge로 이루어진 집합 A를 설정한다. 우선, A를 비어있는 집합으로 초기화시키고greedy한 접근을 통해 A를 순회하며 안전한 edge(u, v)를 A에 추..
그래프 용어 소개그래프 G는 정점 V와 간선 E로 이루어져 있다. 정점 사이를 잇는 간선은 방향을 갖고 이어질 수도 있고, 방향 상관 없이 이어질 수도 있다. 각 그래프마다 노드가 갖는 차수 degree는 Undirected graph에서 edges의 수가 곧 차수이고,directed graph에서는 incoming edges와 outgoing edges로 구분한다. 만약 그래프의 경로에서 모든 정점이 서로 다른 경우 경로가 simple하다고 말한다. 위 그래프에서 같은 경우, 소스 정점을 제외한 cycle의 모든 정점은 simple하다.반대로 사이클이 없는 경우 비순환 acyclic graph 라고 말한다. 그래프 표현 방법 Adjacency-matrix representation 그래프 ..
우리는 하나의 테이블에 얼마나 많은 객체가 저장될지 미리 알 수 없다. 예를들어 같이 일련의 작업이 수행될 때,insert 작업으로 인해 테이블이 가득 찰 수 있다. 이 경우, 추가로 작업을 할당하기 위해서는 테이블을 비우거나 (Contraction) 확장시켜야 (Expansion) 한다. 우리가 배울 Dynamic Tables의 목적은삽입 및 삭제에 따른 amortized cost가 O(1)라는 것을 나타내는 것이다. 공간을 최대한 효율적으로 활용하면서, 사용되지 않는 공간은 항상 할당된 공간의 상수 부분보다 작은 상태를 유지하도록 한다.위의 테이블은 insert와 delete 연산으로 확장될수도, 축소될수도 있다.각각의 연산은 상수 시간에 실행된다. 이런 목표를 달성하기 위해, 우리는 어떻게 테이..
상각(분할 상환) 분석 Amortized Analysis 소개여기에서 말하는 상각분석이란, 알고리즘의 성능을 분석하는 기법 중 하나로주어진 연산에서의 worst case 비용을연산들의 시퀀스 전체에 평균화시켜서 분석하는 방법이다. 간단히 말해서, 평균적인 시간 복잡도를 분석하는 방법이다. 이 방법을 통해 어떤 개별 연산의 비용은 값비쌀 수 있지만, 전체 시퀀스에서의 평균 비용은 낮다는 것을 보여줄 수 있다. 스택 기반 알고리즘에서는 이런 분할 상환 분석이 특히 유용하다. 여기에서 스택 기반 알고리즘이란, 스택 자료 구조를 사용하여 연산을 관리하는 것을 말한다. (후입선출 LIFO) 예시사무실에 10인분 분량의 커피 머신이 있다고 치자.커피 머신이 비어있지 않은 경우 컵에 커피를 붓는 데 10초가 ..