동적 프로그래밍1 동적 프로그래밍(Dynamic Programming)을 이용한 피보나치(Fibonacci) 수 구하기 (Python) 보통 코딩을 배울 때, 피보나치 구현을 배울 때는 재귀(Recursion)를 이용한 방법으로 구현한다. 그러나 재귀 방식의 알고리즘은 시간복잡도가 O(n^2)로 아주 오래 걸리기 때문에 보통은 동적 프로그래밍(DP)를 이용하는 편이다. 동적 프로그래밍의 시간복잡도는 O(n)이다. 재귀 방식의 피보나치 수를 구하는 함수 def recursion(n): if n==1 or n==2: return 1 else: return fibo(n-1) + fibo(n-2) 동적 프로그래밍 방식의 피보나치 수를 구하는 함수 def dp(n): dp = [1,1] if n==1 or n== 2: return 1 for i in range(2,n): dp.append(dp[i-1]+dp[i-2]) return dp[-1] 2022. 1. 11. 이전 1 다음