[JS][프로그래머스][LV.2] 피보나치 수열

업무하면서 내가 짜는 코드가 너무 효율적이지 못한 것 같다는 생각과 함께 다시 풀기 시작한 코테..

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

문제 설명
피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다.

예를들어

• F(2) = F(0) + F(1) = 0 + 1 = 1
• F(3) = F(1) + F(2) = 1 + 1 = 2
• F(4) = F(2) + F(3) = 1 + 2 = 3
• F(5) = F(3) + F(4) = 2 + 3 = 5
  와 같이 이어집니다.

2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요.

제한 사항

• n은 2 이상 100,000 이하인 자연수입니다.

처음에 짠 코드

function solution(n) {
    var answer = F(n);
    return answer;
}

function F(n){
    if(n==0){
        return 0
    }else if(n==1){
        return 1
    }else{
        return F(n-1)+F(n-2)%1234567
    }
}

그냥 문제 읽고 문제를 그대로 코드화, 재귀를 사용 했는데,

.... 시간초과랑 런타임 에러가 나버렸다..

다시 생각해보니 재귀를 쓰면 매번 F(n)을 새로 계산해서 중복 계산을 하니까 시간이 엄청 오래걸린다고 생각을 했다.

이 후 다시 짠 코드

function solution(n) {
    const fibonacci = new Array(n+1).fill(0);
    fibonacci[1] = 1;
    
    for(let i = 2; i <= n; i++) {
        fibonacci[i] = (fibonacci[i-1] + fibonacci[i-2]) % 1234567;
    }
    
    return fibonacci[n];
}

재귀 대산 반복문으로, 배열로 이전 값을 저장하도록 변경하였다.

코드의 시간 복잡도도
재귀 : O(2^n)
반복문: O(n)
으로 확실히 줄었다

결론: 재귀는 만능이 아니다 ( 싸피 할 때도 느꼈지만.. 재활하는 중이니까 다시 상기하기 위해 작성하였다. )