programmers - 동적계획법 - 피보나치 수

피보나치 수는 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을 완성해 주세요.

function solution(n) {
    let answer = 0;
    let arr = [];
    let i = 0;
    let Fibonacci;
    
    if ( n < 2){
        return n % 1234567;
    }
    
    while( i < n + 1 ){
        if( i < 2){
            Fibonacci = i;
            arr.push(i);
            i++;
        }else{
            Fibonacci = arr[i-2] + arr[i-1];
            arr.push( Fibonacci);
            i++;
        }
        
    }
    
    return arr[n] % 1234567;
}

쉽게 봤는데 정확성 점수가 다소 모자랐다. 문제의 요지는 n번째 피보나치 수를 1234567로 나눈 나머지를 마지막에 따로 구하는 것이 아니라 각 피보나치수를 구할 때마다 이 연산을 미리 해놔야 한다는 뜻이다.

아래는 참고한 코드와 수정한 내 코드.

function solution(n){
	let answer = [];
    
    for(let i = 0; i <= n; i++){
      if(i==0) answer.push(0);
      if(i==1) answer.push(1);
      if(i>=2){
        let sum = answer[i-1] + answer[i-2];
      	answer.push(sum % 1234567);
      }
    }
    
    let result = answer[n];
    
    return result 
}

function solution(n) {
    let answer = 0;
    let arr = [];
    let i = 0;
    let Fibonacci;
    
    while( i < n + 1 ){
        if( i < 2){
            arr.push(i % 1234567);
            i++;
        }else{
            Fibonacci = arr[i-2] + arr[i-1];
            arr.push( Fibonacci % 1234567 );
            i++;
        }
        
    }
    
    return arr[n];
}

마지막으로 가장 축약된 코드

function fibonacci(num) {
  if(num < 2) return num;
        
  return (fibonacci(num-1) + fibonacci(num-2)) % 1234567;
}

아래는 python

def solution(n):
    arr = []
    i = 0
    
    while i < n + 1:
        if i < 2:
            arr.append(i % 1234567)
            i += 1
        else:
            Fibonacci = arr[i - 2] + arr[i - 1]
            arr.append(Fibonacci % 1234567)
            i += 1
    
    return arr[n]

유튜브 참고: https://www.youtube.com/watch?v=vYquumk4nWw&list=PLBZBJbE_rGRU5PrgZ9NBHJwcaZsNpf8yD

참고 풀이:https://velog.io/@diddnjs02/%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98-%EC%88%98