피보나치2 백준 [6571번] 피보나치 수의 개수 (Python) 정답률이 생각보다 낮은 문제입니다,, 아마 피보나치를 재귀로 구하다가 시간초과가 많이 나서 정답률이 낮은 것 같네요! 피보나치는 동적 프로그래밍(Dynamic Programming) 방식으로 풀어야 쉽게 통과 될 걸로 보입니다. (피보나치 DP 코딩에 대해 쓴 글입니다. https://yejun402.tistory.com/2) Python Code def dp(a, b): dp = [1,1] cnt = 0 for i in range(2,b+1): if dp[i-1]+dp[i-2] > b: break dp.append(dp[i-1]+dp[i-2]) dp = dp[1:] for i in dp: if a 2022. 1. 11. 동적 프로그래밍(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 다음
