기록은 기억을 지배한다

동적계획법 DP(Dynamic Programming) 이란 어떤 문제를 풀기 위해 과거에 구한 해를 활용하는 방식의 알고리즘을 말한다. 말로 설명하면 이해하기 어려울 수 있기 때문에 가장 대표적인 예시 피보나치 수열을 살펴보겠다. 피보나치 수열은 첫항과 둘째항이 1, 1로 그다음 항부터는 앞의 두 항을 더하는 식이다. f(n) = f(n-1) + f(n-2) 수식으로 표현하면 위와 같다. 123456789101112131415161718192021222324#includeusing namespace std;int f[100]={0}; int fib(int n){ if(n==0) return 0; else if(n==1) return 1; else if(f[n]) return f[n]; else{ f[n]..