Coding StudyRoom

* Greedy algorithm이 중요한 이유 1. 쉽고 빠른 구현: heuristic idea(경험과 지식에 기반) 2. Test-bed: baseline performance 제공. - 연구자들이 가장 먼저 접근하는 설계 전략. 3. May be "optimal" : optimal substructure - local optimal --> global optimal : proof required. ex 1. 도둑 가방(sack) -> 보석방: 보석(무게/부피, 가치) --> 보석 아이템의 일부만 담을 수 있다. (constraint) --> 도둑boss Q: optimal? highest prices? ex 2. startup company: fund raising. --> 투자가: 사업아이템, 전..

D0 -> D1 -> D2 .... (2D matrix로 표현 가능) : D[i,j] = i에서 j까지 가는 가장 짧은 길 Key : - D1[i,j] = i에서 j까지 가는데, 직접 or 1번 도시를 경유할 수 있다. - D2[i,j] = i에서 j까지 가는데 직접 or 1번도시 경유 or 2번도시 경유할 수 있다. ex) D1[5,4] = min(D0[5,4], D0[5,1] + D0[1,4]) D2[5,4] = min(D1[5,4], D1[5,2] + D1[2,4]) Recurrence Equation Dk[i, j] = min(D(k - 1)[i, j], D(k - 1)[i, k] + D(k - 1)[k, j]) k : 경유지 #include #define V 4 // 꼭짓점 총 개수 #defin..

식 : (n, k) = (n-1, k-1) + (n-1, k) 0 비효율적 ---------------------------------------------------------------------------- Dynamic Programming 접근법 (Save and Reuse) - Problem : subproblems recurrence, subproblem overlap이 있음. -> Principle of optimality : 계산을 위해 필요한 cell만 계산하는 코드 최적화가 필요하다!! Step 1 : 주어진 문제로부터 recurrence equation을 유도해냄 - 큰 문제 = 작은 문제 + 작은 문제 .... + 작은 문제 Step 2 : 작은 문제를 먼저 풀고 결과 값들을 저장..