mojo's Blog

Various Costs for a Graph G = (V, E) 임의의 정점 u, v 가 존재할 때 u에서 v로 가는 경로를 찾을때, Adjacency list : O(|V| + |E|), 정점을 전부 탐색하면서 연결된 간선들을 탐색한다. Adjacency matrix : O(|V|^2), 서로 연결된 경우가 1이므로 1인 경우를 모두 탐색한다. Prim's Minimum Spanning Trre Algorithm Idea – In each step, find and add an edge of the least possible weight that connects the (current) tree to a non-tree vertex. Algorithm 꼭짓점들의 집합을 partition 하는 방식이다..

인접 행렬을 이용한 다익스트라 알고리즘을 구현한 코드이다. Solution Code /* Dijkstra's algorithm for a digraph in adjacency matrix */ #include #include void create_graph(void); void display(void); int find_path(int, int, int*, int*); #define MAX 4096 #define TEMP 0 #define PERM 1 struct node { int predecessor; int dist; /*minimum distance of node from source*/ int status; }; int n, adj[MAX][MAX]; void main() { int i, sou..

Kruskal’s Minimum Spanning Tree Algorithm • Idea – Finds an edge of the least possible weight that connects any two trees in the forest. forest 내에서 두 개의 tree로 연결되어진 가중치가 최소가 되는 간선것을 찾는 아이디어를 활용한다. 즉, Disjoint-Set 을 이용하여 해결해야 한다. • Implementation using disjoint-set data structure 0. A 는 초기에 empty set으로 간선(u, v) 을 담기 위한 용도로 사용된다. 1. 먼저 MAKE-SET 함수를 통해 각 정점별로 자기 자신을 가르키도록 하도록(parent[v] = v) 설정한다. 2..

Data Structures for Disjoint Sets • Partition – A partition of a set X is a set of non-empty subsets of X such that every element x in X is in exactly one of these subsets. – Example: X = {1, 2, 3, 4, 5, 6} → { {1, 3, 5}, {2}, {4, 6} } • Disjoint-set data structure (union-find data structure) – Used to effectively manage a collection of subsets that partition a given set of elements. • Basic ope..

Problem – Let J = {1, 2, …, n} be a set of jobs to be served. – Each job takes one unit of time to finish. – Each job has a deadline and a profit. • If the job starts before or at its deadline, the profit is obtained. ➢ Schedule the jobs so as to maximize the total profit (not all jobs have to be scheduled). 예를 들어서 다음과 같은 Job(Deadline, Profit)이 4개 존재한다고 하자 이때, 최대 이익을 낼 수 있는 경우는 job = [4, 1] 인 경우..

Maximum Non-overlapping Intervals 이전에 Earliest finish first 방법이 가장 그럴듯 해 보인 방법임을 확인하였다. 따라서 이에 대한 알고리즘을 알아보도록 한다. Greedy algorithm Input : A = {a1, a2, ..., an} with ai = [si, fi] for 0 ≤ si S = S ∪ {aj}, k = j, aj를 담아주고 담아준 인덱스 j를 k에 넣어준다. (j..