08.05에 푼 문제입니다.
피보나치 수열

기본적인 문제이지만 동적 알고리즘에 대해 추가 공부하려고 풀어봤다!

풀이법

1. 재귀 알고리즘
2. 동적 알고리즘
3. 반복 알고리즘

피보나치 수열은 총 3가지 방법이 있다.
면접으로 나올 수 있는 문제이므로 정리했다!

재귀함수로 풀기 - O(2^n)

재귀함수로 풀게 되면 계산한 값을 따로 저장하지 않는다. 따라서 매번 새로운 계산을 실행해야 한다.

function fibo_recur (n){
	if(n<2) return n
    	return fibo_recur(n-2)+fibo_recur(n-1)
 }

동적 알고리즘 - O(n)

동적 알고리즘은 계산한 값을 배열에 저장한다. 필요한 값이 있으면 바로 꺼내서 사용하면 된다.

function fibo_dp(n){
	if(arr[n]!==-1) return arr[n]
    
    	arr[n]= fibo_dp[n-2]+fibo_dp[n-1]
        return arr[n]
}

반복 알고리즘 - O(n)

반복 알고리즘은 가장 안정성있는 문제 풀이법이다. 앞서 두개의 알고리즘은 stack overflow가 발생할 수 있다.

function fibo_while(n) {
    let fibo = [0,1]
    for(let i=2;i<=n;i++){
        fibo.push(fibo[i-2]+fibo[i-1])
    }
    return fibo[n]
}