물음표 살인마

안녕하세요 오늘은 알고리즘을 풀다보면 자연스럽게 만나게 되는 dp에 대해 알아보도록 하겠습니다. DP, Dynamic Programming, 이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말합니다. 분할정복과 비슷하지만 분명한 차이점은 dp에서는 작은 문제들이 반복되며, 그것을 이용해 문제를 풀어나간다는 점입니다. dp를 사용할 수 있는 가정은 두가지가 있습니다. 1. 큰 문제를 작은 문제로 분할 가능해야 하며, 2. 작은 문제에서 구한 정답이 그것을 포함하는 큰 문제에서도 동일해야 합니다. 그럼 본격적으로 피보나치 수열을 들여다보겠습니다. 저는 피보나치 수열의 26번째자리에 있는 값을 구하고 싶습니다. 이는 dp[26]을 구하기 위한 극히 일부분만을 나타낸 그림임에도 불구하고 dp[2..