문제

피보나치 수는 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 이하인 자연수입니다.

입출력 예

n	return
3	2
5	5

입출력 예 설명

피보나치수는 0번째부터 0, 1, 1, 2, 3, 5, ... 와 같이 이어집니다.

---

나의 풀이

재귀

function solution(n) {
  if (n <= 1) return n;

  return (solution(n - 1) + solution(n - 2)) % 1234567;
}

재귀를 이용한 풀이는 테스트케이스 7번부터 끝까지 시간 초과 에러가 떴다. (역시...) 그래서 메모이제이션으로 다시 풀어보기로 했다.

메모이제이션

function solution(n) {
    const memo = [0, 1];
    
    function fibo(n) {
        if (memo[n] === undefined) {
            memo[n] = fibo(n - 1) + fibo(n - 2) % 1234567;
            // memo.push(fibo(n - 1) + fibo(n - 2) % 1234567);
            return memo[n];
        } else {
            return memo[n];
        }
    }
    
    return fibo(n) % 1234567;
}

메모이제이션을 이용해 풀면 될 거라고 생각했는데, 마지막 테스트케이스 2개가 런타임 에러가 뜨면서 해결이 안됐다..
결국 다른 사람의 코드를 참고해서 풀기로 했다 🥹

---

정답 코드

function solution(n) {
    let memo = [0, 1];

    function fibo(n) {
        for(let i = 2; i <= n; i++) {
            memo[i] = (memo[i - 1] + memo[i - 2]) % 1234567;
        }
    
        return memo[n];
    }
    
    return fibo(n);
}

이 풀이는 반복문으로 풀었다.
피보나치 문제는 무조건 재귀로 풀어야하는 줄 알았는데.. 찾아보니 반복문을 이용한 풀이가 메모이제이션 & 재귀를 이용한 풀이보다 시간 복잡도가 더 빠르다고 한다.

• 반복문을 사용하는 경우에는 중복 계산 없이, 한 번 계산한 값을 배열에 저장하여 재사용하기 때문에 시간복잡도가 O(n)이 되고,

• 재귀를 사용하는 경우에는 재귀 호출에 의해 함수가 여러 번 호출되기 때문에 시간 복잡도는 O(2ⁿ)이라고 한다.

• 메모이제이션 + 재귀를 사용하는 경우에는 각각의 수를 계산할 때마다
  1) 이미 계산한 값인지 확인하고,
  2) 이미 계산한 값이라면 해당 값을 재사용하기 때문에
  중복 계산을 피할 수 있으므로 O(n)의 시간복잡도가 걸린다.
  하지만 재귀 호출에 따른 함수 호출 비용이 증가하기 때문에 결론적으로 반복문보다는 오래 걸린다.

따라서 반복문을 이용한 풀이가 재귀 & 메모이제이션을 이용한 알고리즘보다 효율적이며 더 빠른 실행 속도를 가지게 된다.