leko

function fib(n) a = 1, b = 1; if (n == 1 || n == 2) return 1; for i = 3 to n c = a + b; a = b; b = c; return c;​ iterative function fib(n) if (n == 1 || n == 2) return 1; else return fib(n-1) + fib(n-2); What’s the time complexity? T(n) = T(n-1) + T(n-2) + 1 minimum cost between stations int cost[N][N] = { {0, 10, 75, 94}, {-1, 0, 35, 50}, {-1, -1, 0, 80}, {-1, -1, -1, 0} }; minCost(0, N-1) = MI..

무방향 (양수) 가중치 그래프 G =(V, E) 각 edge (u, v) ∈E에 대해서 가중치 : W(u, v) 문제 : edge들의 부분집합 T ∈ E를 찾아라 1. T에 속한 edge들에 의해 모든 정점들이 서로 연결된다 2. 가중치의 합 ∑ w(u, v) 이 최소가 되도록 한다 (u, v)∈ T 3. 입력 : n개의 도시 도시와 도시를 연결하는 도로비용 문제 : 최소의 비용으로 모든 도시들이 연결되게 한다 어떤 부분집합 A에 대해 A ∪{(u, v)} 도 역시 MST의 부분집합일 경우 edge (u, v)는 A에 대해서 안전한다 generic -mst (G, W) A