반응형
피보나치 수열 dp
-
[ Algorithm ] 피보나치수열 알고리즘 비교 (재귀, DP, 반복)공부 !/Computer Science 2022. 4. 22. 20:55
피보나치수열 알고리즘 비교 (재귀, DP, 반복) 피보나치 수열에 많이 사용되는 알고리즘 3가지를 비교해보자 ! 피보나치 수열은 첫번째와 두번째 값이 1이며 이후는 f(n) = f(n-1) + f(n-2) 점화식을 갖는다 피보나치 수열에 많이 사용되는 3가지 알고리즘은 재귀, 반복, DP가 존재하는데 먼저 3가지 알고리즘의 복잡도를 비교해보면 재귀 O(2ⁿ) DP O(n) 반복 O(n) 이다 재귀 & DP & 반복 차이점 일반적으로 재귀는 함수가 함수 내에서 자신을 호출하는 것으로 동일한 함수가 여러번 반복되는 것이다 DP 는 큰 문제를 작은 문제로 쪼개고 그 답을 저장해두었다가 재활용한다 그렇기 때문에 재귀에서 동일한 문제가 여러번 반복된다는 비효율적인 부분을 DP로 해결할 수 있다 DP 로 작은 문제..