피보나치 구현으로 알아보는 동적 프로그래밍

1) 재귀

class Solution {
    public int solution(int n) {
        return fibonacci(n);
    }
    public int fibonacci(int n)
    {
        if (n == 1 || n == 0)
            return n;
        return fibo(n - 1) + fibo(n - 2);
    }
}

if (n == 4)

fibo(4) = fibo (3) + fibo(2)

fibo(3) = fibo(2) + fibo(1) | fibo(2) = fibo(1) + fibo(0)

fibo(2) = fibo(1) + fibo(0)

fibo(2)가 두번 호출된다. 즉, 하위 문제들의 중복으로 인해 O(2^n)의 시간복잡도를 가지게 된다.

• n의 숫자가 커질 수록 메모리 속도가 느려진다.
• 중복되는 부분을 제거하면 보다 효율적으로 프로그램을 짤 수 있다.
• 이 때 사용되는 방법 중 하나가 DP(Dynamic Programming)이다.

2) 동적 계획법(Dynamic Programming)

DP란? 작은 문제들을 풀다보면 같은 문제들을 반복해서 푸는 경우가 생긴다. 이 문제를 해결하기위해 중복되는 값을 저장한 뒤 재사용하는 기법을 말한다.

2.1) Top-down(Memorization) 방식

문제애 접근 할 때, 큰 문제에서 작은 문제로 내려가는 순으로 해결하는 방법

class Solution {
    static int[] memo;
   	int max = 100001;
    
    public int solution(int n) {
        memo = new int[max];
		
        return fibo(n) % 1234567;
    }
    public int fibonacci(int n)
    {
        if (n == 1 || n == 0)
            return n;
        else if (memo[n] != 0)
            return memo[n];
        
        return memo[n] = (fibo(n - 1) + fibo(n - 2)) % 1234567;
    }
}

시간 복잡도는 O(N)

2.2) Bottom-up(Tabulation) 방식

class Solution {
    static long[] dp;
    int max = 100001;
    
    public int solution(int n) {
        dp = new long[max];
    
        return (int)fibonacci(n);
    }
    public long fibonacci(int n)
    {
 		dp[0] = 0;
        dp[1] = 1;
        
        for (int i = 2; i <= n; i++)
            dp[i] = (dp[i - 1] + dp[i - 2]) % 1234567;
        
        return dp[n];
    }
}

재귀 호출을 하지 않기 때문에 Top-down 방법보다 시간과 메모리 사용량을 줄일 수 있다.