거누의 개발노트

DP DP, 즉 다이나믹 프로그래밍(또는 동적 계획법)은 기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것으로 특정한 알고리즘이 아닌 하나의 문제해결 패러다임으로 볼 수 있다. 피보나치 수열로 예를 들어 본다면, def fibo(n): if n in [1, 2]: return 1 return fibo(n-1) + fibo(n-2) assert fibo(10) == 55 assert fibo(100) == 354224848179261915075 # 안끝난다. 이런식으로 재귀 함수로 푼다면 100번째 값을 찾을 때는 fibo(1)번째, fibo(2)번째를 찾았던 n번째수를 계속해서 찾아나갈 것이다. 그렇지만 찾아 나간 결과를 저장..