[알고리즘] DP (Dynamic Programming) 동적 계획법

DP란?

부분 문제의 결과 값을 이용해 전체 문제를 풀어나가는 알고리즘 방법이다.

두 번 이상 계산되는 부분 문제를 중복되는 부분 문제 (overlapping subproblems)라고 한다. 이를 한 번만 계산하여 저장하고 다음에는 이 결괏값을 이용해서 풀이하면 된다.

 

메모이제이션(Memoization)

이미 계산한 값을 저장해두었다가 재활용하는 최적화 기법을 메모이제이션(Memoization)이라 한다. 

 

 1) 특정 함수가 호출되었을 때, 배열에 해당 값이 저장되어 있는지 확인. 존재한다면, 해당 값을 return.

 2) 존재하지 않는다면, 값을 계산하고 배열에 저장한 뒤 해당 값을 return.

 

- 메모이제이션은 입력이 고정되어 있을 때, 그 결과가 항상 같은 함수, 참조적 투명 함수(referential transparency)에만 적용 가능하다.

 

- 항상 기저 사례(base case)를 가장 먼저 처리해야 함.

* 기저 사례란 어떤 것의 바닥이 되는 부분으로, 더 이상 쪼갤 수 없는 조건을 의미

 

 

 

 

 

dp를 풀이하기 위한 접근 방식으로는 아래와 같이 2가지가 존재한다. dp풀이 예시로 많이 드는 피보나치 수로 간단하게 감(?)을 잡아본다.

 

 

1. Top-Down

재귀와 같은 호출 방식으로 큰 문제에서 내려오는 방식이다.

long fibo(int n){
    if (n == 1 || n == 2)
        return 1;
    if (memo[n])
        return memo[n];
    memo[n] = fib(n-1) + fib(n-2);
    return memo[n];
}

 

2. Bottom-Up

top-down과 반대로 작은 문제부터 계산해서 올라가는 방식이다.

long fibo(int n) {
    memo[0] = 0;
    memo[1] = 1;
    for (int i = 2; i <= n; i++) 
        memo[i] = memo[i - 1] + memo[i - 2];
    return memo[n];
}

 

 

 

 

 

DP를 사용할 때

-구하고자 하는 문제를 부분 문제로 나눈다

-base case(가장 먼저 구해지는 부분 문제, 종료 조건)을 구해 저장한다 -> 메모이제이션

-인접항들의 계산식인 점화식을 구한다

ex) 피보나치에서  memo [i] = memo[i - 1] + memo[i - 2]; 이부분이 각 항의 값을 인접항들의 계산된값(메모이제이션의 결과) 즉, 점화식이 된다.

-만약 memo[i] = Math.min(memo [], memo []); 이런 식으로 사용될 경우 memo배열을 Integer.MAX_VALUE 등으로 초기화해서 사용하기