Sean :: Dev

※ 귀찮아도 직접 손으로 쓰고 그리며 생각해야 이해가 빠르다 Example 1 : Knapsack (배낭 문제) Dynamic Programming 무게와 가치가 정해진 N개의 물건이 있을때, 가치의 총합이 max가 되도록 배낭을 싸는 문제. 이때, 배낭의 무게 제한은 K이다. (각 물건은 1개씩만 존재하며, 배낭에 넣거나/안넣거나) 동전교환문제와 마찬가지로 Greedy한 방법으로 해결되지않음. ex) V[N] = {13,8,6,12} W[N] = {6,4,3,5} D[i][j] = i번째 물건까지 넣을지/안넣을지 정했을때, 무게 j이하를 채우는 가치의 합중 최대값 => 점화식 : D[i][j] = Max(D[i-1][j], D[i-1][j-W[i]]+V[i]) Max에서 비교하는 두 값중, 전자는 이전..

Dynamic Programming (동적계획법) 복잡한 문제를 여러개의 작은부분문제(sub-problem)으로 나누어 해결하는 기법. 이미 계산된 부분 문제가 다시 발생하면, 새롭게 계산하지않고 이전의 계산값을 참조해 이용할 수 있다. DP를 통해 부분문제를 다시 해결하는 시간을 절약할 수 있지만, 이전 계산값을 저장할 공간이 필요하므로 Time - Space간의 trade off라고 할 수 있다. ex. 피보나치 단순탐색으로 구현시, 위와 같이 여러번 계산된다. => Memorization : 한번 계산된 값을 기록해두고 이후 중복호출 되었을때 새롭게 계산하는게 아닌 저장해둔값을 가져와 사용한다. fibonacci_topdown Top-Down / Bottom-Up Top-down 방식은 큰 문제에서..