프로그래머스 피보나치 수 - 자바스크립트 풀이

https://school.programmers.co.kr/learn/courses/30/lessons/12945

프로그래머스

 

처음에 이와 같이 재귀함수로 풀었으나

function solution(n) {
    if(n <= 1) return n;
	else return (solution(n-1) + solution(n-2)) % 1234567;
}

 

시간 초과 👿

시간 초과(런타임 에러)가 발생하여 코드를 아래와 같이 수정하였다.

자바스크립트 코드 풀이

function solution(n) {
    let prev = 0, cur = 1;
    
    for(let i = 2; i <=n; i++){
        const next = (prev + cur) % 1234567;
        prev = cur;
        cur = next;
    }
    
    return cur;
}

 

 

 

초기에 F(0) = 0 , F(1) = 1이므로 prev = 0, cur =1 로 변수를 선언한다. 

let prev = 0, cur = 1;

이후 값 2부터 for문을 돌면서 각각 피보나치 수를 구한다.

for(let i = 2; i <=n; i++){
	const next = (prev + cur) % 1234567;
    prev = cur;
    cur = next;
}

prev, cur 값을 업데이트 해주면서 n-1, n-2일때 피보나치 계산 결과를 매번 새로 계산하지 않고 prev, cur 값을 가져다가 쓰기 때문에  메모이제이션이 없는 위의 재귀함수 코드에 비해 효율적이다 👍.