[동적계획법] 피보나치수

1. 문제

피보나치수
https://school.programmers.co.kr/learn/courses/30/lessons/12945

2. 기존 풀이

이 풀이는 동적 계획법으로 풀었다.

하지만 변수는 이 언어가 javascript라는 점이었다.
약 9900정도부터 recursion이 javscript의 recursion limit을 초과하여 런타임에러가 발생하게 된다.

파이썬의 경우는 setRecursionLimit을 지정하여 이 문제를 해결할 수 있지만, javascript는 따로 그런 방식을 두고 있지 않다.

그래서 해당 풀이를 통해 동적계획법 알고리즘이 무엇인지 확인하고 복습한데에 의미를 두고, for문을 돌려 하나씩 확인하는 방법을 채택하게 되었다. 생각해보면 피보나치수열의 경우, for문을 돌리는게 O(n) 시간복잡도가 발생하므로 더 나을 거 같고, 동적계획법으로 하면 n제곱으로 경우의 수가 늘어나기 때문에 O(n**2) 시간복잡도가 나오지 않을까 예상한다.

function solution(n) {
    var answer = 0;

    const result = new Array(100001).fill(null)
    result[0] = 0
    result[1] = 1
    result[2] = 1
    
    function F(n){
        if(result[n] !== null){
            return result[n]
        }
        result[n] = (F(n-1)%1234567 + F(n-2)%1234567)%1234567
        return result[n]
    }
    
    answer = F(n) 
    return answer;
}

3. 개선 풀이

그리고 % 연산의 특징은 하단처럼 피연산자들에 나머지 연산을 하고 연산한 결과값에 또 %을 해도 값은 동일하게 나온다는 것이다.

function solution(n) {
    var answer = 0;
    const res = [0,1]
    for(let i = 2; i <= n ; i++){
        res.push((res[i-1]%1234567+res[i-2]%1234567)%1234567)
    }
    answer = res[n]
    return answer;
}