dynamicprogramming

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번째 피보나치 수를 구하는 문제가 되고 다른 수를 구할 때 같은 문제가 겹치는 ..