Programmers - 피보나치수

💡 What Is Dynamic Programming and How To Use It 영상을 참고하였습니다.
by CS Dojo

1. Recursion(재귀함수)
2. Memoization(메모이제이션: 동일한 연산을 반복할 때 값을 저장)
3. Bottom-Up(트리구조-bottom-up)

---

1. Recursion(재귀함수)

처음에 피보나치란 단어를 보자마자 아래와 같이 코드를 바로 작성해서 제출을 했었다.

const fibonacci = (n) => {
    if (n <= 1) {
        return n;
    }
    return fibonacci(n - 1) + fibonacci(n - 2);
} 

역시 제출하니 10문제 중에서 7번부터 모두 실패와 런타임 에러가 나타났다. 재귀함수의 깊이가 너무 깊은게 문제였나 싶었다. 위에 작성한 함수의 시간복잡도를 생각해보면 $O(2^n)$으로 굉장히 비효율적이다.

---

2. Memoization(메모이제이션: 동일한 연산을 반복할 때 값을 저장)

그래서 다음으로 시도를 해본 것은 Memoization이다. 재귀호출이 반복되면 불필요한 계산들이 수없이 반복되고 수가 1000으로만 커져도 recurion error가 발생할 것이다. 중간에 계산된 값들을 저장해서 필요할 때 참조하는 방법이 바로 Memoizaiton이다. 코드는 아래와 같다.

const memoizationFibonacci = (n, memo = []) => {
    let result = 0;
    if (memo[n] !== undefined) {
        return memo[n];
    }
    if (n <= 1) {
        result = n;
    }
    else {
        result = memoizationFibonacci(n - 1, memo) + memoizationFibonacci(n - 2, memo);
    }
    memo[n] = result;
    return result;
}   // O(2n + 1)

memo란 list를 이용해서 중간에 새로운 값들을 저장하는 것이다. 이 방법의 시간복잡도는 $O(2n+1)$이다. 그 이유는

    if (memo[n] !== undefined) {
        return memo[n];
    }

위 코드블럭이 작동할 경우는 1번이다. 그리고 아래 코드블럭이 작동할 경우는

if (n <= 1) {
        result = n;
    }
    else {
        result = memoizationFibonacci(n - 1, memo) + memoizationFibonacci(n - 2, memo);
    }
    memo[n] = result;
    return result;

$n$번이다. 그리고 result = memoizationFibonacci(n - 1, memo) + memoizationFibonacci(n - 2, memo); 이 line을 읽게 되면 최대 2번 작동하기 때문에 시간복잡도는 $O(2n+1)$ 이 된다.

---

3. Bottom-Up(트리구조-bottom-up)

마지막으로 Bottom-Up 방법이다. 흔히 동적프로그래밍이라 알려져있다. 피보나치 수열을 트리구조로 그려봤을 때 n이 5라고 가정을 하고

fib_1() -> fib_2() -> fib_3() -> fib_4() -> fib_5() 와 같이 탐색을 하면 총 n번이 소요된다. 따라서 하나의 배열안에 1부터 n까지의 결과를 저장해 원하는 값을 찾는 것은 크기 n인 배열을 한번 순회하는 것이다. 코드로 작성하면 아래와 같다.

const bottomupFibonacci = (n) => {
    if (n <= 1) {
        return n;
    }
    let bottomupList = [];
    bottomupList[0] = 0;
    bottomupList[1] = 1;
    // for loop to n
    for (let i = 2; i <= n; ++i) {
        bottomupList[i] = bottomupList[i - 1] + bottomupList[i - 2];
    }
    return bottomupList[n];
}   // O(n) : travel only once

0 과 1은 이미 주어진 상태이므로 for문은 2부터 n까지 진행한다. 이렇게 하면 시간복잡도 $O(n)$에 해당하는 가장 빠르게 피보나치 수를 구할 수 있다.

하지만 위에 있는 코드로 답안을 제출한다면 정답으로 인정이 안될 것이다. 위에 코드에서 아래와 같이 수정을 해주어야한다.

 bottomupList[i] = bottomupList[i - 1] % 1234567 + bottomupList[i - 2] % 1234567;

피보나치 연산에 있어서 큰 수가 오게되면 런타임에러라고 하면서 멈출 것이다. 그래서 나머지 연산을 추가해주었다.