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

동적 계획법, DP란?

다이나믹 프로그래밍이란, 하나의 문제를 여러 작은 파트로 나누어서 그 결과를 저장하여 하나의 문제를 해결하기 위한 알고리즘이 아닌 문제해결 방식 중 하나이다.

일반적인 재귀 방식과 매우 유사한데, 큰 차이점은 일반적으로 재귀를 단순히 사용할시 동일한 작은 문제들이 여러번 반복 되어 비 효율적인 계산이 될 수 있다는 것이다.

DP를 사용하기 위해서는?

겹치는 부분, 즉 문제에서 동일한 반복이 일어나는지 파악해야한다. 또한, 부분 문제의 최적 결과 값을 사용해 문제의 최적 결과를 낼 수 있어야 한다.

DP는 부분 문제의 결과를 저장하여 재 계산하지 않아야 하는데, 부분 문제가 반복적으로 나타나지 않는다면 재사용이 불가함으로 사용할 수 없다.

앞에서 말했듯이, DP는 알고리즘이 아닌 문제해결 방식 중 한가지이기 때문에, 다양한 문제에서 사용이 가능하며 적용이 가능한지의 여부를 알아내는 것과, 그 방식 자체가 어려워지는 코드일 수도 있다.

---

 

DP의 등장은 피보나치 수열을 통해 알 수 있다. 2항까지는 1을 더하고, 3항부터는 바로 앞의 두 항을 더한 수로 정의되는데, 아래와 같은 수열로 이루어진다.

(0), 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89...

이런 피보나치 수열을 보통 프로그래밍에서는 재귀함수를 통해 표현하곤 하는데 그 코드도 간단하다.

int fibo(int n) {
    if (n<=2) {
      return 1;
    } else {
      return fibo(n-1) + fibo(n-2);
    }
   }

이 계산은 fibo(4) 연산이 두 번, fibo(3) 연산이 세 번 진행되기 때문에 중복되는 계산이 존재한다. 이런 반복되는 결점을 보완하기 위해서 이 DP, 동적 계획법이 생겨난 것이다. 이런 DP를 적용해 위의 식에 중복을 없애고자 하면 이러하다.

int fiboData[100] = {0,};

int fibo(int n) {
  if (n<=2) 
    return 1;
  if (fiboData[n]==0)
    fiboData[n] = fibo(n-1) + fibo(n-2);
  return fiboData[n];
}

fiboData라는 배열을 생성하여 연산되는 값들을 저장한다.

if문을 통해 n이 2 이하라면 1을 반환하고, 그 이상일 경우 fiboData에 연산값이 있는지 확인한다.

없으면 새로 연산해서 저장하고 반환한다.

---

Memoization

동일한 문제를 반복해야 할 경우, 한 번 계산된 결과를 저장해 두었다가 활용하는 방식으로 중복 계산을 줄이는 것을 뜻하는 Memoization

TOP-DOWN

가장 큰 문제를 보고, 작은 문제를 호출해 답을 찾는 방식이다. 재귀 호출을 이용해 구현한다.Bottom-up 방식보다 점화식을 이해하기 쉽다는 장점이 있다.

public int top_down(int num) {
    if(num == 1) return 0;
 
    if(dp[num] > 0) return dp[num];

    
    dp[num] = top_down(num-1) + 1;
    if(num%3 == 0) {
    	int cnt = top_down(num/3) + 1;
        if(dp[num] > cnt) dp[num] = cnt;
    }
    
    if(num%2 == 0) {
    	int cnt = top_down(num/2) + 1;
        if(dp[num] > cnt) dp[num] = cnt;
    }
    
    return dp[num];
}

주어진 값(n) 을 1로 만드는데 최소 연산 횟수를 구한다.

n이 3으로 나누어 떨어지면 n = n/3

n이 2로 나누어 떨어지면 n = n/2

그 외라면 n = n-1

Bottom-up

문제를 작은 파츠부터 차례대로 풀어 조금씩 큰 전체를 연산한다. top-down에서 재귀 호출을 주로 사용했다면 반복문을 사용한다.

public void bottom_up() {
    int cnt = 0;
    int[] dp = new int[N+1];

    for(int i=2; i<N+1; i++) {
        cnt = MAX;

        if(i%3 == 0) {
            cnt = dp[i/3];
        }

        if(i%2 == 0 && cnt > dp[i/2]) {
            cnt = dp[i/2];
        }

        if(cnt > dp[i-1]) {
            cnt = dp[i-1];
        }

        dp[i] = cnt+1;
    }
}

반복문을 사용해서 i를 2~N 까지 순회한다.

3개의 조건문이 참인 경우, 이전에 저장된 값을 저장한다. 2번째 조건문부터는 cnt와 dp[m] 와 비교하며 최초 연산 횟수를 dp 배열에 저장한다.