Dynamic Programming

동적 계획법 - DP

입력크기가 작은 부분 문제들을 해결한 후, 해당 부분 문제의 해를 활용해서
보다 큰 크기의 부분 문제를 해결, 최종적으로 전체 문제를 해결하는 알고리즘

• Memoization 기법을 사용한다
• 상향식 접근법이다
• 프로그램 실행시 이전에 계산한 값을 지정하며, 다시 계산하지 않도록 전체 실행 속도를 빠르게 하는 기술

ex) 피보나치 수열

DP예시

메모화기법을 사용한 피보나치 수열

• 재귀 형태

static int[] arr = new int[10000];
private static int fibonacci(int n){
    if (n >= 2) {
        if (arr[n] == 0) {
            arr[n] = fibonacci(n - 1) + fibonacci(n - 2);
            return arr[n];
        }
        else
            return arr[n];
    }
    else if (n <= 1) {
        if (n == 1)
            arr[n] = 1;
        return (arr[n]);
    }
    return 0;
}

• 반복문 형태

private static int fibo(int n)
{
    int[] arr = new int[n+1];
    arr[0] = 0;
    arr[1] = 1;

    for (int i = 2; i < n + 1; i++)
        arr[i] = arr[i-1] + arr[i-2];
    return arr[n];
}