[이코테] 다이나믹 프로그래밍(Dynamic Programming)

중복되는 연산 줄이기 탑다운 보텀업 다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예시로 피보나치 수열이 있다. 피보나치수열은 이전 두항의 합을 현재의 항으로 설정하는 특징이 있는 수열이다. ex) 1 1 2 3 5 8 13 21 34 55 89... 수학적 점화식을 프로그래밍으로 표현하려면 재귀 함수를 사용하면 간단하다. #재귀 함수를 이용한 피보나치 구현 def fibo(x): if x == 1 or x == 2: return 1 return fibo(x-1)+fibo(x-2) print(fibo(4)) 하지만 피보나치 수열의 코드를 이렇게 작성하면 심각한 문제가 생길 수 있다. 바로 f(n)에 함수에서 n이 커지면 커질수록 수행 시간이 기하급수적으로 늘어나기 때문이다. 이러한 문제는 다이나믹 프로..