본문 바로가기

알고리즘

 (26)
7-2강 - Greedy Algorithm 2 (Scheduling) 4. Minimizing Total Time in the system 0) 문제 소개 j1~jn : job t1~tn : job 소요 시간 w1~wn : 각 job을 하기 전에 기다리는 시간 1) Algorithm 정렬하고 실행 시간이 짧은 것 먼저 시작한다. 2) Multiprocessor Scheduling processor가 여러개 있어도 마찬가지로 실행 시간이 짧은 것부터 각 processor에 job을 할당합니다. 5. Scheduling with Deadlines 0) 문제 소개 d1~dn : deadline p1~pn : 각 job 별로 d1~dn 안에 job을 완료하면 p1~pn이라는 이득을 얻는다. S : job들의 부분집합 feasible set : S의 모든 job들을 deadline..
7-0강 - Greedy Algorithm 0 (그리디 알고리즘) 0. Greedy Algorithm (대부분의 문제는 일련의 선택으로 구성되어 있는데) 현재 상황에서 가장 좋은 것을 선택 => 선택의 결과가 전체로 보았을 때 좋지 않을 수도 있습니다. 1) Optimality 1> global optimal & 2> local optimal 2) (Combinatorial) Optimization Problem 0> combinatorial : solution이 discrete & finite set이다. 1> 구성 [1] input [2] constraint [3] objective [4] output : [1]로 인해, [2]를 만족하는, [3]을 최소/최대화 하는 solution 2> solution feasible solution : constraint를 만족..
6-9강 - [중요] Dynamic Programming 9 (Directed Acyclic Graphs) 9. Directed Acyclic Graphs : cycle이 없는 graph 1) Activity On Vertex (AOV) Vertex : action Edge : precedence relation 0> 기본 용어 i = j의 predecessor (j = i의 successor) i = k의 immediate predecessor (k = i의 immediate predecessor) 1> relation - partial order [1] transitive (iRj & jRk => iRk) [2] irreflexive (iRi가 항상 성립하지 않는다.) 2> topology order 아래 조건을 만족하는 linear ordering "i = j의 predecessor" => "i prec..
6-5강 - Dynamic Programming 5 (The Traveling Salesperson Problem, TSP) 5. The Traveling Salesperson Problem (TSP) 0) The Traveling Salesperson Problem 1> tour (Hamiltonian cycle) 모든 vertex를 한 번씩 지나는 cycle 구하기 2> optimal tour minimum length(cost)로 tour를 만들기 => TSP : optimal tour 찾기 1) The Principle of Optimality 1> 전제 : T = [v1, vp1, vp2, ... , vpn-1, v1] = optimal tour => P = [vp1, vp2, ... , vpn-1, v1]라는 path가 minimum length(cost) 2> 가정 : P'라는 다른 path가 length(cost..
6-3강 - Dynamic Programming 3 (the principal of optimality, 행렬 곱셈) 간혹 Dynamic Programming을 적용할 수 없는지 알아내는 방법이 바로 The Principle of Optimality입니다. cf> The Principle of Optimality instance 전체에서 optimal solution이면 → subinstance 한정해서도 optimal solution이어야 한다. 1> 예제 1 - P(s, t)가 shortest path -> P(s, w)와 P(w, t) 모두 shortest path (True) - reverse : P(s, w)와 P(w, t) 모두 shortest path -> P(s, t)가 shortest path (False) 2> 예제 2 - Floyd's shortest path problem Dk (i, j)가 i에서..
6-2강 - Dynamic Programming 2 (최단거리 유형, 플로이드 알고리즘 ) 2. All Pairs Shortest Paths 0) 최단 경로 문제 유형 1> Shortest path finding problem u와 v간의 최단 경로 찾기 2> Single source all destination shortest path problem 하나의 출발점(single source)에서 각 정점(all destination)까지 도달하는데 (필요한 비용을 계산하여) 최단 경로들을 구합니다. 3> All pairs shortest paths problem 모든 점들간의 거리 중 최단거리(경로)를 구하는 문제 cf> 최단 경로 문제의 공통적인 solution step 1 : shortest path의 distance(cost)를 구하기step 2 : 그 distance(cost)를 가지는..
6-1강 - Dynamic Programming 1 (DP, Binomial Coefficient) 0. Dynamic Programming (instance I [size는 n]이 있을 때,) 1) bottom-up 방식 - recursive property 1> bottom-up으로 cost 계산 instance I에 대한 optimal solution은 I의 sub-instance에 대한 optimal solution을 이용하여 푼다. 2> top-down으로 sol 구한다. sub-instance에 대한 cost를 모두 구해놓고 (bottom-up) 이들을 고려하여 다시 top-down으로 optimal solution을 구한다. 2) Programming = array(table) 1> Divide & Conquer와 다른 점 sub-instance들이 중복되며 solution을 구한다. 2>..
5-1강 - Divide and Conquer 0 (Solving Recurrences Equations) 0. Solving Recurrences Equations 0) Solving Recurrences by Induction 이렇게 풀기는 너무 어렵습니다. 그래서 general term 구하는 다른 방법들에 대해 하나씩 알아보겠습니다. 1) Using Characteristic Equation - 문제 : Homogeneous Linear Recurrences 1> Theorem 1(서로 다른 근을 가지는 경우) → [1] r (r0 ~ r_k-1)에 관한 equation으로 만들고 r들(r0 ~r_k-1)을 구한다. → [2] 위 theorem에 따라 t_n을 만든다. → [3] t0 ~ t_k-1 초기값 대입 → [4] k개의 선형 연립 방정식을 통해 c1 ~ ck를 구한다. ( tn의 general..

티스토리툴바