본문 바로가기

전체 글

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.
Unsupervised Learning of Depth and Ego-Motion from Video Zhou, Tinghui, et al. "Unsupervised learning of depth and ego-motion from video." Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2017. Link Abstract 이 논문에서는 monocular depth, camera motion estimation을 위한 unsupervised learning framework를 제공한다. Monocular video sequence만으로 end-to-end learning을 통해 unsupervised learning을 실현한다. KITTI dataset 에서 supervised learning와 비슷한 성.. Computer Vision/3D Vision 2020. 9. 30.
Color * 이 포스트는 컴퓨터 비젼에 대한 개인 학습용으로 작성한 포스트입니다. Color Color : 여러 가지 정의가 있을 수 있지만, "interaction between physical light in environment & visual system"이라 정의할 수 있다. Color는 Hue, Value, Chroma(Saturation) 3가지 성분으로 나눌 수 있다. Hue는 color의 이름, Value는 color의 밝기정도, Saturation는 color의 pure 정도를 나타낸다. Color mixing : 색을 혼합하는 걸로 Adding과 Multiplying이 있다. Adding은 일반적으로 빛을 혼합하는 것이고, Multiplying은 색을 혼합하는 것이다. (물감을 섞는것은 mul.. Basic Learning/Computer Vision 2020. 9. 29.
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.

티스토리툴바