다이나믹 프로그래밍 한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘 다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예시로는 피보나치 수열이 있다 피보나치 수열의 점화식은 다음과 같다 재귀함수를 이용해서 코드로 나타낼 수 있다 def fibo(x): if x == 1 or x ==2 : return 1 return fibo(x-1)+fibo(x-2) print(fibo(4)) 하지만 위와 같이 작성하면 f(n) 함수에 n이 커지면 커질수록 수행 시간이 기하급수적으로 늘어나기 때문에 심각한 문제가 생길 수 있다. 시간복잡도는 O(2ⁿ) 정도로 소요된다. 위의 코드를 다시 생각해보면 동일한 함수가 반복적으로 호출된다. 이미 한번 계산했지만, 계속 호출할 때마다 계산을 다시 한다. fibo(6)을 구..