justgo_developer

동적계획법1. 일반적으로 최적화문제(최소값,최대값) 혹은 카운팅 문제에 적용됨2. 주어진 문제에 대한 순환식을 정의한다.3. 순환힉을 memoization 혹은 bottom-up 방식으로 푼다. - subproblem들을 풀어서 원래 문제를 푸는 방식, 그런 의미에서 분할정복법과 공통성이 있음- 분할정복법에서는 분할된 문제들이 서로 disjoint하지만 동적계획법에서는 그렇지 않음- 즉 서로 overlapping하는 subproblem들을 해결함으로써 원래 문제를 해결 분할정복법동적계획법 Optimal Substructure- 어떤 문제의 최적해가 그것의 subproblem들의 최적해로부터 효율적으로 구해질 수 있을 때 그 문제는 optimal substructure를 가진다고 말한다.- 분할정복법/탐욕..

행렬 경로 문제 - 정수들이 저장된 n x n 행렬의 좌상단에서 우하단까지 이동한다.단 오른쪽이나 아래쪽 방향으로만 이동할 수 있다.- 방문한 칸에 있는 정수들의 합이 최소화되도록 하라. Recursive algo. int mat(int i, int j){if (i==1 && j==1)return m[i][j];else if(i==1)return mat(1,j-1) + m[i][j];else if(j==1)return mat(i-1,1) + m[i][j];elsereturn Math.min(mat(i-1,j) , mat(i,j-1) ) + m[i][j]; } => 비효율적 Memoization:계산된 결과값을 캐시에 저장int mat(int i, int j){if(L[i][j] != -1)return L..

동적계획법(DP) Fibonacci Numbers->recursion으로 하니 많은 계산이 중복됨Memoization: 중간 계산 결과를 cahing함으로써 중복 계산을 피함bottom-up 방식배열을 이용해 순환식을 bottom-up방식으로 계산하는 것은 동적계획법이라ㅗㄱ 한다. 이항계수(Binomial Coefficient)->많은 계산이 중복됨 Memoization Dynamic Programming Memoization vs Dynamic Programming- 순환식의 값을 계산하는 기법들이다.- 둘 다 동적계획법의 일종으로 보기도 한다.- Memoization 은 top-down방식이며, 실제로 필요한 subproblem만을 푼다.- 동적계획법은 bottom-up 방식이며, recursion에..