프로그래머스_Level.2 피보나치 수

1.문제설명

문제: 피보나치 수

programmers.co.kr/learn/courses/30/lessons/12945?language=javascript

코딩테스트 연습 - 피보나치 수

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

 

2. 제한 조건

* n은 1이상, 100000이하인 자연수입니다.

 

3.입출력 예

n	return
3	2
5	5

 

📌나의 풀이

처음에는 재귀 함수를 이용해서 코드를 작성했다. 하지만 테스트케이스 7번 부터 실패가 뜨기 시작했다.

검색을 해보니 재귀함수는 O(2^n)의 시간 복잡도를 가지고있다. 즉 엄청 비효율적이다. 

이 문제를 풀기 위해서는 O(n)의 시간 복잡도로 풀어야한다.

 

재귀함수 사용 방법

function fibo(n){
    if(n<=1){
        return n;
    }
    
    //재귀함수를 통해 값을 구한다.
    return fibo(n-1)+fibo(n-2);
}

function solution1(n) {
    var answer = 0;
  
    answer = fibo(n); 
    return answer;
}

재귀함수를 사용하면 간변하지만 함수가 한 번 호출되면 다시 두번 호출되기 때문에

지수적으로 증가해 시간복잡도는 O(2^n)이 된다. 문제를 풀때는 사용하면 시간초과로 실패한다.

 

 

반복적 풀이 방법

function solutio2n(n) {
    var answer = 0;
    
    //a는 F(0)을 의미하며 b는 F(1)을 의미한다.
    var a=0,b=1;
    
    //n-1까지 순차적으로 F(n)을 하며 값을 구한다.
    for(var i=0; i<n-1; i++){
        var temp = a+b;
        a = b;
        b = temp;
    }
   
    return b;
}

n-1만큼 반복문을 시행하는 이유는 n번재 값 a와 첫 번째 값 b를 계속 반복하면서 원하는 값을 만드는데,

n 이 2일 때는 단 한번(n-1)만 계산 하면 원하는 값을 만들 수 있기 떄문이다.

재귀함수에 비해 매우 효율적이다. 시간 복잡도는 O(n)이다. 이 방법을 사용하면 문제를 해결 할 수 있다. 

 

반복적 동적 계획법 풀이

 

function solution(n) {

	//n+1만큼의 배열을 만든다
    var cache = new Array(n+1);
    cache[0] = 0; //F(0)
    cache[1] = 1; //F(1)
    
    for(var i=2; i<n+1; i++){
        cache[i] = cache[i-1]+cache[i-2];
    }
    
    return cache[n];
}

배열의 크기를 n+1로 설정하는 이유는 우리가 원하는 n번쨰 값을 n번째 배열에 저장하기 위해서 이다.

이 방법을 사용해도 문제를 해결 할 수 있다.

💡배운점

• 피보나치 수를 재귀 함수 방법이 아닌 다른 방법으로 풀 수 있는 법에 대해서 알게되었다. 
• 각 방법들에 시간복잡도를 알게되었다.

✔참고 자료

shoark7.github.io/programming/algorithm/%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EC%9D%84-%ED%95%B4%EA%B2%B0%ED%95%98%EB%8A%94-5%EA%B0%80%EC%A7%80-%EB%B0%A9%EB%B2%95