DP

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 package backjun; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class backjun_1520_내리막길 { private static int column; private static int row; private static ..

Dynamic Programming : 작은 문제의 답을 조합해서 큰 문제의 답을 푸는 과정이다. DaC(Divide and Conquer) 과 DP(Dynamic Programming)은 비슷하지만 다음의 차이점이 존재한다. DaC 1. 문제가 절반으로 줄어든다. 2. Function Problem 3. 결과가 한번 사용된다. 4. 분할이 성능을 향상 시킨다. DP 1. 문제가 -1로 줄어든다. 2. 최적화 문제 3. 결과가 여러번 사용된다. 4. 결과 재사용이 성능을 향상시킨다. Overlapping Subproblem 은 중복되는 부분 문제이다. 예를 들면 N번째 피보나치수를 구하는 문제를 구하는 문제는 N-1번째 N-2번째 피보나치 수를 구하는 문제가 되고 다른 수를 구할 때 같은 문제가 겹치는 ..