문제

연습문제
https://programmers.co.kr/learn/courses/30/lessons/12945

---

접근

피보나치 수를 재귀적으로 구하는 방법은 너무 유명하기도 해서 왜 레벨2 문제인가 하고 그냥 시작했는데...

재귀함수 ?

def solution(n):
    def fib(num) :
        if num < 2 :
            return num
        else :
            return (fib(num-2) % 1234567 + fib(num-1) % 1234567) % 1234567
        
    return fib(n)
    
테스트 1 〉	통과 (0.03ms, 10.2MB)
테스트 2 〉	통과 (0.07ms, 10.1MB)
테스트 3 〉	통과 (0.20ms, 10.2MB)
테스트 4 〉	통과 (0.05ms, 10.2MB)
테스트 5 〉	통과 (0.11ms, 10.2MB)
테스트 6 〉	통과 (0.29ms, 10.2MB)
테스트 7 〉	실패 (시간 초과)
테스트 8 〉	실패 (시간 초과)
테스트 9 〉	실패 (시간 초과)
테스트 10 〉	실패 (시간 초과)
테스트 11 〉	실패 (시간 초과)
테스트 12 〉	실패 (시간 초과)
테스트 13 〉	실패 (런타임 에러)
테스트 14 〉	실패 (런타임 에러)

처음에는 모듈러 연산을 사용하지 않아서 시간초과가 난 것인가 했지만 아니었다.

모듈러 연산(Moudular Arithmetic) 의 특징

1. (a % c + b % c) % c = (a + b) % c
2. (a % c - b % c) % c = (a - b) % c
3. (a % c * b % c) % c = (a * b) % c

일단 모듈러 연산을 사용하는 이유는 문제의 배려다. x % n의 값의 범위는 당연하겠지만 x의 값이 아무리 커져도 n 보다는 작다. 피보나치 수는 값의 크기가 기하급수적으로 커지기 때문에 int의 범위를 넘어버리면 (python에서는 아니겠지만) 우리가 원하는 값이 출력되지 않을 것이니...

배열

나는 피보나치 수를 담을 배열을 만들어서 풀었다.
동적계획법이나 일반항을 이용해서 푸는 여러가지 방법들이 있는데 다음에 아래 글을 다시 참고하면 좋을 것 같다.

피보나치 수열 알고리즘을 해결하는 5가지 방법

---

코드

js

function solution(n) {
    let fibNum = [0, 1]
    function fib(num) {
        if(num < 2){
            return fibNum[num];
        }
        let temp = 0;
        for(var i=2; i < num+1; i++){
            temp = ((fibNum[i-2] % 1234567) + (fibNum[i-1] % 1234567)) % 1234567;
            fibNum.push(temp);
        }
        return fibNum;
    }
    fib(n)
    return fibNum[n]
}

---

python

def solution(n):
    fib_list = [0,1]
    def fib(num) :
        if num < 2 :
            return fib_list[num]
        for i in range(2, num+1) :
            temp = (fib_list[i-2] % 1234567 + fib_list[i-1] % 1234567) % 1234567
            fib_list.append( temp )
        return fib_list
    
    fib(n)
    return fib_list[-1]
    

---