DP ,Subproblem을 그대로 합치면 되는 DP

 

먼저 DP, 즉 Dynamic Programming이 무엇인지 알아볼까요?

큰 문제에 대한 답을 얻기위해 동일한 문제이지만 크기가 더 작은 문제들을 해결한 뒤, 그 결과들을 이용해 큰 문제를 비교적 간단하게 해결하는 기법.

실생활로 드는 예시는 스케줄링 문제, 금융 투자, 게임 전략 등 실생활에 많이 사용하고 있습니다.

 

문제로도 예시를 들어볼까요? 예를들어 1부터 N까지의 곱을 구하는 코드를 작성해본다면 

N이 5라면, 1*2*3*4*5입니다

result=1;
for(i ~ N)
	int tmp = i*result;
    retulr+=tmp;

 

로 쉽게 구할수있겠죠 하지만 큰 단위에서 작게 생각해보자면 점화식을 이용할수있을것입니다. 

N을 구하는 함수를 F(N)으로 가정한다면,

F(N) = F(N-1)*N (if N>1),

F(1) =1

을 이용해서도 풀수 있습니다. 간단한 점화식을 이용한 큰 문제를 간단하게 해결하는 방법이라고 말할수있죠

 

이제 저는 수많은 Dynamic Programming중 Subproblem을 다뤄보는 DP를 공부해볼것입니다.

다양한 코딩 문제중 피보나치 수열 구하기, 계단 오르기, 사각형 채우기 ,서로 다른 BST 개수 세기 등이 존재합니다. 

아까 말한 예시를 점화식을 2개의 방법을 이용하여 풀수있습니다.

 

1. 반복문을 이용한 코드

 

F[1] = 1
for(int i = 2; i <= n; i++)
    F[i] = F[i - 1] * i

System.out.println(F[n]);

 

2. 재귀함수를 이용한 코드

int F(int n) {
    if(n == 1)
        return 1;
    else
        return F(n - 1) * n;
}

System.out.println(F(n));

 

무엇을 이용하든 똑같습니다. 하지만 저희는 "점화식"을 기반으로 풀이를 진행했다고 생각해볼 수있습니다. DP는 점화식이 대부분 필요하다고 이해하시면될것같습니다.

 

 

메모이제이션의 등장 

 

하지만 점화식으로만 DP를 풀기에는 당연히 힘듭니다. 지금처럼 N이 작은경우에는 시간복잡도와 상관없이 해결할수있지만 만약 N이 500~1000정도로 잡고 해결한다면 어떻게될까요? 당연히 1분이상이 걸립니다. 여기서 우리는 이미 계산햇던 부분은 내가 가지고있는게 좋지않을까란 생각이듭니다. 

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

무슨 이야기를 하고싶은거냐면  윗 코드 피보나치 수열을 알고있다는 가정하에 말씀드리겠습니다. N=9일때의 가정입니다.

피보나치 9

당연히 밑에있는 수가 더많지만 시간상 간단하게 말씀드려보겠습니다. 빨간색들은 이미 우리가 알수있는 수들입니다. 근데 굳이 내가 아는 수를 또 계산해야하나요? 아닙니다. 이미 아는 수는 우리가 갖고있어야합니다. DP의 점화식을 풀이하던중 우리가 알고있는 수는 중복으로 생각하여 제거하면됩니다. 이것이 바로 메모이제이션입니다.

N이 7일때의 값을 memo라는 배열을 이용해 볼수있습니다. 

 

이를 가능하게하기위해선 길이가 9인 배열을 총 -1로 초기화 합니다. ( 그 이유는 피보나치 수열은 0부터 점점 증가하는 수이기때문에 -1로 초기화하는게 편하십니다) 

 

int Fibbo(int n) {
    if(memo[n] != -1)          // 이미 n번째 값을 구해본 적이 있다면
        return memo[n];        // memo에 적혀있는 값을 반환해줍니다.
    if(n <= 2)                 // n이 2이하인 경우에는 종료 조건이므로 
        memo[n] = 1;           // 해당하는 숫자를 memo에 넣어줍니다.
    else                       // 종료조건이 아닌 경우에는 
        memo[n] = Fibbo(n - 1) + Fibbo(n - 2);  // 점화식을 이용하여 답을 구한 뒤
                                                // 해당 값을 memo에 저장해줍니다.
    return memo[n];                             // memo 값을 반환합니다.
}

 

이미 구한적이 있는 수라면? (memo[n] != -1)을 이용하여 중복을 제거합니다. 굳이 계산했던 값을 계산할필요가 없던 부분이죠 ! 이는 기존의 피보나치 O(n^2) 시간복잡도였던 수열을 이제는 O(n)로 시간복잡도를 줄일수있는 장점을 가질수있습니다.

이런 식으로 값을 기록하고 기록한 값을 참조하는 것을 메모이제이션이라고 합니다. 

 

Tabulation은 무엇이야?

재귀함수를 이용해  동적계획법을 해결했듯이, for문 (반복문)을 이용해서 동적계획법을 사용할수있습니다. 순서대로 배열에 값을 채워 나가는 방식이라고도 하는데요 이를 Tabulation이라고도 합니다. 

 

int[] dp = new int[MAX_N];

dp[1] = 1;
dp[2] = 1;

for(int i = 3; i <= n; i++)
    dp[i] = dp[i - 1] + dp[i - 2];

System.out.println(dp[n]);

 

이 둘의 차이점을 알고계시나요? 조금만 생각해본다면 메모이제이션은 N=9일때부터 쭉쭉 내려갑니다 하지만 Tabulation은 for문으로 쭉쭉 올라갑니다.  이를 Top - down 방식, Bottom-up 방식이라고도합니다. 이론적인 시간복잡도는 두 방법은 똑같으나. 재귀함수는 좀더 여러번 사용하여 함수 처리에 추가적인 시간이 붙어 Bottom-up 방식이 더 빠릅니다. 하지만 특정 문제의 경우 한 방법으로 푸는 방법이 더 쉬울때가 있으니 모두 다 알아야합니다 !