코딩 테스트

[프로그래머스 Level 2] 피보나치 수

y_flm 2025. 3. 25. 17:14
문제:
피보나치 수는 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을 완성해 주세요.

 

문제 풀어보기: https://school.programmers.co.kr/learn/courses/30/lessons/12945

 

풀이보기

 

더보기
function solution(n) {
    let value = {};
    
    for(let i = 2; i <= n; i++) {
        value[0] = 0;
        value[1] = 1;
        value[i] = (value[i - 1] + value[i - 2]) % 1234567;
    }
    
    return value[n];
}

처음에는 객체를 사용해서 맵핑 시켜주는 방식을 선택했다.

근데 이렇게 연속되는 인덱스 값에서는 객체보다는 배열이 효율적이라고 해서 배열로 바꿔주었다.

 

function solution(n) {
    let value = [0, 1];
    
    for (let i = 2; i <= n; i++) {
        value[i] = (value[i - 1] + value[i - 2]) % 1234567;
    }
    
    return value[n];
}

주의할 점은 return 값에만 value[n] % 1234567을 해줬었는데 그러면 value[n]의 값이 너무 커져서 오버플로우가 발생한다.

따라서 값을 저장할 때부터 % 1234567을 해주면서 값이 커지는 것을 방지해줘야한다!