[ps java] 피보나치 수열 알고리즘(재귀, DP)

우리가 일반적으로 알고 있는 피보나치 수열에 대한 재귀 알고리즘은 다음과 같다

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        System.out.println(fibonacci(n));
        br.close();
    }

    private static int fibonacci(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }

        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

 

하지만 이 코드의 문제점은 재귀 호출을 반복해 시간 복잡도가 어마어마하게 높다는 것이다.

O(2^N) 시간 복잡도를 가지기 때문에 n값이 50만 되더라도 꽤 오래 기다려야 한다

 

 

 

그렇다면 이 코드를 DP로 바꾸면 어떻게 될까? 먼저 DP의 개념을 정확하게 알고 넘어가자

ㅇ동적 프로그래밍(DP, Dynamilc Programming): 복잡한 문제를 더 간단한 하위 문제로 나누고, 그 하위 문제들의 결과를 저장하여 중복 계산을 피함으로써 효율적으로 문제를 해결하는 방법

언뜻 보기에 많은 시간(심지어 지수 시간)이 소요될 것 같은 문제에 주로 적용한다

 

[적용의 조건 3가지]

1. 부문제 단순성(simple subproblems): 부문제들이 j, k, l, m 등과 같은 몇 개의 변수로 정의될 수 있는 경우

2. 부문제 최적성(subproblem optimality): 전체 최적치가 최적의 부문제들에 의해 정의될 수 있는 경우

3, 부문제 중복성(subproblem overlap): 부문제들이 독립적이 아니라 상호 겹쳐질 경우 (따라서 해가 "상향식"으로 구축되어야 함)

e.g. 피보나치 수열에서 n번째 수 찾기, 그래프의 이행적 폐쇄 계산

 

[DP의 두 가지 주요 구현 방법]

- 메모이제이션(memoization): 재귀호출

하향식 접근 방식(Top-Down Approach)이다

 

- 타뷸레이션(tabulation): 반복문

상향식 접근 방식(Bottom-Up Approach)이다

 

위의 코드를 DP의 타뷸레이션을 이용하여 구현해 보면 다음과 같다

import java.io.*;

public class Main2 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        System.out.println(fibonacci(n));
        br.close();
    }

    private static int fibonacci(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }

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

n에 4를 입력한 case

 

재귀호출로 깊게 안 들어가고, 그냥 이전의 결괏값을 활용해 바로 연산을 해버리니 속도가 말도 안 되게 빠른 것이다. 실제로 시간 복잡도는 단지 반복문 O(N) 뿐이며, 50을 입력했을 때 전과 다르게 바로 결괏값이 출력되는 것을 알 수가 있다.

 

이처럼 DP는 굉장히 효율적인 알고리즘이기 때문에 잘 알아두어야 한다. 중복 계산이 많은 문제에서는 과장을 조금 보태서 "DP보다 빠른 방법은 없다" 단순 재귀나 브루트포스를 사용하면 지수 시간이 걸리지만, DP로 하면 주로 다항 시간에 해결이 가능하기 때문이다. 그러니 DP가 많이 어려울지라도, 모두 잘 숙지하도록 하자!