[99클럽 코테스터디 21일차 TIL / 백준] 1003 - 피보나치 함수 (DP)

99클럽 코테스터디 21일차 TIL
KeyWord : 동적프로그래밍(DP)

문제

다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다.

int fibonacci(int n) {
    if (n == 0) {
        printf("0");
        return 0;
    } else if (n == 1) {
        printf("1");
        return 1;
    } else {
        return fibonacci(n‐1) + fibonacci(n‐2);
    }
}

fibonacci(3)을 호출하면 다음과 같은 일이 일어난다.

• fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다.
• fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다.
• 두 번째 호출한 fibonacci(1)은 1을 출력하고 1을 리턴한다.
• fibonacci(0)은 0을 출력하고, 0을 리턴한다.
• fibonacci(2)는 fibonacci(1)과 fibonacci(0)의 결과를 얻고, 1을 리턴한다.
• 첫 번째 호출한 fibonacci(1)은 1을 출력하고, 1을 리턴한다.
• fibonacci(3)은 fibonacci(2)와 fibonacci(1)의 결과를 얻고, 2를 리턴한다.

1은 2번 출력되고, 0은 1번 출력된다. N이 주어졌을 때, fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다.

각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. N은 40보다 작거나 같은 자연수 또는 0이다.

출력

각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.

 

---

 

풀이

문제에 주어진 피보나치 메소드를 동적 프로그래밍(DP) 기법을 이용해 시간복잡도를 줄이는 문제다.

DP의 기본은 이미 계산된 값을 재사용하는 것으로, DP 문제라는 생각이 들면 값을 어떻게 재사용할 수 있을지 고민을 하면 된다.

일단 DP로 구현해보기 전에 문제에 주어진 피보나치 메소드를 살펴보자.

int fibonacci(int n) {
    if (n == 0) {
        printf("0");
        return 0;
    } else if (n == 1) {
        printf("1");
        return 1;
    } else {
        return fibonacci(n‐1) + fibonacci(n‐2);
    }
}

이 메소드는 n=0 혹은 n=1이 될때까지 계속해서 재귀 호출을 진행한다. 이렇게 코드만 보았을 때는 별 문제가 없어 보인다.

하지만 fibonacci()가 재귀 호출되는 깊이를 보면 말이 달라진다.

          fib(5)
         /       \
     fib(4)    fib(3)
     /    \      /    \
fib(3)  fib(2) fib(2) fib(1)
  /   \     /   \
 fib(2) fib(1) fib(1) fib(0)
  /   \
 fib(1) fib(0)

n=5일 때 fibonacci()메소드가 호출되는 과정을 시각적으로 나타낸 것이다.

재귀호출이 될때마다 엄청난 양의 피보나치 메소드가 쌓이는 것을 볼 수 있다.

수학적으로 계산을 해보면 대략 $2^{5-1}$회의 피보나치 메소드가 호출된다. 즉, n이 5만 되어도 피보나치 메서드는 약 16회 호출된다.

만약 n이 더 커진다면? 10만 되어도 약 512회, 11이면 1024회, 12면 2048회다. 이 문제의 최댓값인 40만 되어도 $2^{39}$이다. 아무리 컴퓨터의 연산이 빠르다고 해도 이 정도의 연산량감당하는 것은 힘들어 보인다.

 

이제 동적 프로그래밍을 활용하여 개선해보자.

fib(5)일 때 호출되는 fib(1)과 fib(0)의 횟수를 세어보자. fib(1)은 4번, fib(0)은 2번 호출되었다. 여기서 중요한 점은 동일한 메서드를 여러번 실행한다는 것이다.

즉, 비효율적이다.

그렇다면 fib(0)과 fib(1)의 값은 미리 계산하여 저장해둔 후, fib(0), fib(1)이 호출되는 상황에서 이 계산된 값을 바로 꺼내어 사용하면 어떨까?

또다시 살펴보자. fib(5)에서 fib(2)는 3번 호출된다. 여기서 fib(2)의 값도 저장하여 활용한다면 더 빨라질 것이다. 그리고 fib(2)는 fib(0) + fib(1)이므로, 이 값을 구하는 것은 저장된 값을 가져와 더해주는 것으로 쉽게 게산할 수 있다.

• fib(0) = dp[0] = 0
• fib(1) = dp[1] = 1
• fib(2) = dp[2] = dp[0] + dp[1]
• fib(3) = dp[3] = dp[2] + dp[1] = dp[0] + dp[1] + dp[0]

식으로 나타내면 이렇게 될 것이다.

한 번 fib(2)를 호출하면 dp[2]에 값을 저장하고 이 값을 추후에 재활용한다.
한 번 fib(3)을 호출하면 dp[3]에 값을 저장한다. fib(3)을 처음 호출했을 때는 fib(2) + fib(1)이 호출되는 것이 아니라 dp[2] + dp[0]이 수행된다.

이렇게 하면 불필요한 재귀호출을 생략할 수 있다. 이렇게 따로 값을 저장하고 재활용하는 방식을 메모제이션이라고 한다.

이를 생각하며 코드로 구현해주면 된다. n=40까지 메모제이션을 한 후, 해를 출력하면 된다. 나는 출력에서 소모되는 시간을 줄이기 위해서 StringBuilder로 모은 후 한 번에 출력을 해주었다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(br.readLine());
        int[][] dp = new int[41][2];

        dp[0] = new int[]{1, 0};
        dp[1] = new int[]{0, 1};

        for (int i = 2; i < 41; i++) {
            dp[i][0] = dp[i-1][0] + dp[i-2][0];
            dp[i][1] = dp[i-1][1] + dp[i-2][1];
        }


        for (int i = 0; i < T; i++) {
            int N = Integer.parseInt(br.readLine());
            sb.append(dp[N][0]).append(" ").append(dp[N][1]).append("\n");
        }
        System.out.println(sb);
    }
}