피보나치 수열을 어떻게 표현할 수 있을까? F(n) = F(n-1) + F(n-2) 니까 대부분, 재귀함수로 구현한다.int F(int n){if(n == 1 || n == 2)return 1;elsereturn F(n-1) + F(n-2);} 근데, 이러면 중복된 연산이 많아진다. Time Complexity = O(2^(n/2)) 이라고 한다. DP를 쓰면 문제가 쉽게 해결된다.이전의 계산되는 F(n)값을 return하는게 아니라 배열에 저장하고다음 계산때는 배열에 저장한 값을 활용한다.이렇게 문제를 해결하면 아래와 같다. memset(DP, -1, sizeof(DP));DP[1] = DP[2] = 1;int F(int n){if(DP[n] == -1)DP = F(n-1) + F(n-2);elsere..
