[Python]알고리즘/이코테 2021
[다이나믹 프로그래밍] 예제1 - 피보나치 수열
[이코테] 예제1 - 피보나치 수열 (한줄평) 다이나믹 프로그래밍의 대표적인 예제로 어렵지 않게 풀 수 있는 문제 (풀이1) 단순 재귀 풀이 시간: 1분 이내 1) 문제 해결 아이디어 단순 재귀 함수로 구현했을 때 시간복잡도는 O(2**n)이다. 이미 계산한 것에 대해 호출할 때마다 또 계산을 하기 때문에 n이 커질수록 수행 시간이 기하급수적으로 늘어나는 문제가 있다. 예를 들어, f(6)을 호출할 때 f(3)이 3번이나 호출된다. f(100)이라면 어마어마한 연산을 수행하는데 수백억년이 넘어간다. 2) 소스코드 # 1. 피보나치 수열(단순 재귀) def fibo(x): if x == 1 or x == 2: return 1 return fibo(x - 1) + fibo(x - 2) print(fibo(4..
