프로그래머스 Level 2 | 피보나치 수 JS

피보나치 수

문제 설명

피보나치 수는 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, ... 와 같이 이어집니다.

---

좋은 문제라고 생각해서 작성합니다.

피보나치 수열은 원하는 값을 알아내기 위해서 앞의 두 수를 알아야만 한다.
가장 간단하면서 쉬운 피보나치 코드는 아래와 같다.

const fb = (n) => {
    if(n < 2) {
      return n;
    }
      return fb(n - 1) + fb(n - 2);
}

작은 수 라면 크게 문제 없이 동작하겠지만 조금만 수가 커져도 처리능력이 매우 떨어지는걸 직접 확인할 수 있다.
재귀를 사용하기 때문에 반복적으로 원하는 값을 계산하기 때문

---

function solution(n) {
    const numArr = [0, 1];
    
    if(n < 2) {
        return n;
    } else {
        for(let i=2; i<=n; i++) {
            numArr[i] = numArr[i - 1] + numArr[i - 2];
        }
    }
    return numArr[n];
}

위와 같이 이미 계산된 결과를 배열안에 저장하면 한번 계산한 값을 다시 계산해야 하는 일이 없다.
이를 Memoization | 메모이제이션라고 함.
간단하지만 작은 차이하나로 효율성이 크게 달라지기 때문에 중요.

---

///프로그래머스에서 요구하는 정답 코드
function solution(n) {
    const numArr = [0, 1];
    
    if(n < 2) {
        return n;
    } else {
        for(let i=2; i<=n; i++) {
            numArr[i] = (numArr[i - 1] % 1234567) + (numArr[i - 2] % 1234567);
        }
    }
    return numArr[n] % 1234567;
}