본문 바로가기

Basic Learning/Algorithm Design

Minimum Spanning Tree & Clustering * 이 포스트는 알고리즘의 기초에 대한 개인 학습용으로 작성한 포스트입니다. Minimum Spanning Tree Spanning tree : 최소 개수의 edge를 사용하여 모든 node를 커버하는 tree (graph) Minimum spanning tree : 사용된 edge cost의 합이 최소가 되는 spanning tree * Cayley's Theorem : Complete graph에는 가능한 spanning tree가 $n^{n-2}$개 존재한다. Edge의 cost가 모두 다르다는 가정하에, Cut property : Subset S와 G - S를 잇는 edge가 여러개 있을 때 (cutset), cost가 제일 작은 edge를 e라 하자. 그러면 MST는 e를 포함한다. Cycle .. Basic Learning/Algorithm Design 2020. 10. 8.
Optimal Caching & Shortest Paths in Graph * 이 포스트는 알고리즘의 기초에 대한 개인 학습용으로 작성한 포스트입니다. Optimal Caching k item을 수용할 수 있는 cache가 있다. Request가 왔을 때, cache에 있는 item이면 cache hit, 없으면 cache miss라 한다. Cache miss 시에 request한 item을 cache에 보관하기 위해 보관되어 있던 item을 eviction한다. 이때, 목표는 Cache miss 횟수가 최소화 되도록하는 Eviction schedule을 찾는 것이다. Farthest in Future : 제일 오랫동안 request되지 않을 item을 evict시키는 방법 => FF (Farthest in Future)은 optimal eviction schedule이다. R.. Basic Learning/Algorithm Design 2020. 10. 7.
Greedy Algorithms * 이 포스트는 알고리즘의 기초에 대한 개인 학습용으로 작성한 포스트입니다. Interval Scheduling 시작시각과 종료시각이 존재하는 job이 여러개 있을 때, 시간이 겹치는 job은 overlap될 수 없다. 이 때, 최대로 실행할 수 있는 job subset을 구하는 문제이다. 이 문제를 풀기위해 다음 4개의 Greedy 전략을 생각할 수 있다. 1. Start time이 빠른 job 우선 2. Finish time이 빠른 job 우선 3. Job 실행시간이 작은 job 우선 4. Conflict가 작은 job 우선 1, 3, 4번은 반례를 통해 Optimal이 아니라는 것을 보일 수 있다. Interval Scheduling의 Greedy alogrithm은 Finish time이 빠른 순.. Basic Learning/Algorithm Design 2020. 9. 29.
Graphs * 이 포스트는 알고리즘의 기초에 대한 개인 학습용으로 작성한 포스트입니다. Graph Representation Adjacency matrix : (u, v)에 edge가 있으면 $A_{uv} = 1$로 채움 Space proportional : $n^2$ Checking edge : $\Theta (1)$ Identifying all edges : $\Theta (n^2)$ Adjacency List : edge로 연결된 node끼리 list로 연결 Space proportional : $n + 2m$ Checking edge : $O(deg(u))$ Identifying all edges : $\Theta (m + n)$ Connected : 모든 pair 사이에 path가 존재할 때, connec.. Basic Learning/Algorithm Design 2020. 9. 25.
Basics of Algorithm Analysis * 이 포스트는 알고리즘의 기초에 대한 개인 학습용으로 작성한 포스트입니다. Asymptotic Order of Growth Polynomial-Time : input size N에 대해 running time이 $cN^d steps$로 bound되는 constant c > 0, d > 0가 존재한다. => Running time이 polynomial할 때, 해당 알고리즘은 'efficient하다' 라고 한다. Asymptotic order의 정의들 Upper bounds $T(n) = O(f(n))$ : if there exist constant $c>0$ and $n_0 \geq 0$ such that for all $n \geq n_0$ we have $T(n) \leq c \cdot f(n)$ L.. Basic Learning/Algorithm Design 2020. 9. 24.
Five Representative Problems * 이 포스트는 알고리즘의 기초에 대한 개인 학습용으로 작성한 포스트입니다. Interval Scheduling Start time과 finish time이 정해진 job이 주어졌을 때, overlap되지 않는 최대의 cardinality를 구하는 문제이다. 예를 들어, 아래 그림에서 overlap되지 않고 최대로 실행될 수 있는 set of jobs은 {b, e, h}이다. Weighted Interval Scheduling 위의 문제에서 각 job이 weight를 가지고 실행되는 job의 weight가 최대가 되는 문제이다. 모든 job의 weight를 1로 두면 위의 문제 Interval Scheduling과 같아진다. Bipartite Matchinig 아래 그림의 Bipartite graph(서.. Basic Learning/Algorithm Design 2020. 9. 24.
Stable Matching Problem * 이 포스트는 알고리즘의 기초에 대한 개인 학습용으로 작성한 포스트입니다. Stable Matching Problem Stable matching problem은 두 개의 집합에서 서로의 선호도가 있다고 가정했을 때, 최선의 짝을 짓도록하는 문제이다. 다르게 말하면, 선호도에 근거한 더 나은 짝이 없는 상태를 만드는 것이다. Unstable pair : 짝이 지어진 상태에서 X-Y는 서로 짝이 아닌데 X는 현재 상태보다 Y를 더 선호하고, Y는 X를 더 선호하는 짝을 말한다. Stable assignment : 어느 하나도 unstable pair가 없도록 만드는 것이다. Perfect matching : 집합의 모두가 1:1로 matching한 상태 Stable matching : Perfect ma.. Basic Learning/Algorithm Design 2020. 9. 21.

티스토리툴바