다이나믹 프로그래밍

다이나믹 프로그래밍이 필요한 이유공간을 희생해서 시간을 벌자.현실의 문제들 중에 그대로 컴퓨터로 해결하기에는 어려운 것들이 많다. 해를 구하는데 시간이 오래 걸리거나 메모리 공간을 매우 많이 필요한 경우가 그러하다. 그래도 메모리공간을 담보로 연산속도를 향상 할 수 있는 방법들이 존재한다. 다이나믹 프로그래밍이 그 중에 하나다.적용조건1. 큰 문제를 작은 문제로 나눌 수 있다.2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.기본 아이디어Memoization, DP table피보나치 수열을 예를 들자. 피보나치 수열은 연속 된 두개의 항이 그 다음 항의 합인 수열이다.f(n) = f(n-1) + f(n-2), f(1) = 1, f(2) = 1피보나치 수열은 재귀함수로 구현할 수 있다..