[DP] Dynamic Programming에 대해서

DP란 ?

어떤 문제를 풀기 위해 그 문제를 더 작은 문제의 연장선으로 생각하고, 과거에 구한 해를 활용하는 방식의 알고리즘(나무 위키)

 

동적 프로그래밍은 동일한 결과를 다시 계산하지 않도록, 하위 문제로 나누고 하위 문제의 결과를 저장하여 주어진 복잡한 문제를 해결하는 알고리즘 패러다임(divide and conquer와 유사, 하위 문제로 나누고 하위 문제의 솔루션을 결합하는 관점에서 유사)

 

Mathematical Background [수학적 배경]

 

피보나치 수열 F(n) = F(n-1) + F(n-2) n>=2, F(1) = 1, F(0) = 0을 보면, 재귀적인 함수 호출이 있습니다.

앞선 두 숫자의 합으로 주어지는 일련의 숫자로 정의할 수 있습니다.

F(2) = F(1) + F(0), F(3) = F(2) + F(1)

피보나치 수열 구조

F(5)를 계산하기 위한 과정

F(5)를 계산하기 위해서는 F(4), F(3), F(2)의 값을 계산해야 하고, 값을 계속 호출해야 합니다. fib(5)의 하위 구조는 fib(4), fib(3)과 같고, fib(4)의 하위구조는 fib(3), fib(2), fib(3)의 하위구조는 fib(2), fib(1)과 같습니다.

 

이렇게 값을 지속적으로 계산하게 된다면, 불필요한 계산이 증가하고 효율성(시간 복잡도) 측면에서 떨어진다고 볼 수 있습니다. 그래서 값의 결과를 메모리에 저장하면 이에 대한 문제점을 해결할 수 있습니다.

 

해결 방안

1. Memorization(Top-Down) : 문제를 처음 해결할 때 마다 결과를 메모리에 저장하고, 다음에 문제를 조회할 때 마다 간단히 조회

2. Tabulation(Bottom-Up) : 솔루션을 선형 방식으로 미리 계산하고, 나중에 조회를 수행하기 위해 테이블에 저장

 

그러면 동적 프로그래밍은 언제 사용할까 ?

 

Overlapping Subproblems(중복 하위 문제), Optimal Substructure(최적 구조(탐욕 알고리즘의 유용성을 결정하는데 만족)) 속성을 만족할 때 사용합니다.

 

Memorization -> 기존 피보나치 수열과 유사하지만, 이전에 해결한 하위 문제에 대한 솔루션을 저장하는 조회 테이블을 유지 관리한다는 관점에서 차이점을 가집니다. 동일한 하위 문제를 여러 번 해결하는 대신, 한 번 해결하고 나중에 재사용할 수 있도록 답을 저장

 

Memorization 설계 방법

1. 조회 테이블의 모든 요소 값을 -1로 초기화
2. 메모리제이션을 수행하는 재귀 함수 f(n)을 호출
3. 모든 단계 i에서 f(i)는 먼저 솔루션이 저장되어 있는지 확인하기 위해 조회 테이블을 조사
4. f(i)가 -1이 아닌 경우(솔루션에 값이 저장된 경우), 값을 반환 
5. 솔루션에 저장되지 않은 경우 f(i)는 i가 기본 조건을 충족하는지의 여부를 확인
6. 기본 조건을 만족하는 경우 조회 테이블을 기본 값으로 업데이트
7. 그렇지 않으면, f(i)는 문제 i를 하위 문제로 분할하고 재귀적으로 자신을 호출한다.
8. 재귀 호출이 반환된 후 f(i)는 하위 문제에 대한 솔루션을 결합하고 조회 테이블을 업데이트하고 문제 i에 대한 솔루션을 반환

 

Tabulation 설계 방법 (조회 테이블을 상향식으로 작성)

 

기본 문제에 대한 솔루션으로 시작 -> 상위 문제에 대한 솔루션을 계산하는데 사용

 

1.  조회 테이블에서 i의 기준 값을 입력
2.  i의 나머지 값을 반복하는 루프를 실행
3. 모든 반복 i에서 이전에 해결된 하위 문제에 대한 솔루션을 사용하여 조회 테이블의 i 번째 항목 업데이트
4. 루프가 끝나면 값을 반환 

Tabulation vs Memorization 

 

Tabulation : 기본값을 먼저 초기화해준다는 관점에서, memorization과 차이가 있습니다. (Tabulation에서는 dp[0] = 0, dp[1] = 1로 초기화 해주고 재귀 호출) 그리고 상향식 방식으로 작동하기에 모든 하위 문제에 대한 솔루션을 계산해줘야 하는 단점이 있습니다.

그러나 여러 검사 및 조회를 수행하지 않는다는 장점이 있습니다. 

 

Memorization : 하향식 방식으로 작동하므로 여러 검사 및 조회를 수행, 최악의 경우 메모리제이션이 모든 문제를 해결하지만, 최상의 경우에는 그렇지 않다(Tabulation은 모두 해결). Tabulation 솔루션보다 더욱 직관적이다. 

 

<코드>

#include <iostream>

#define value -1
#define max 100

int dp_m[max];

using namespace std;

int dp_Memorization(int n)
{
    if(dp_m[n] == value)
    {
        if(n<=1) dp_m[n] = n; // dp[1] = 1 ,dp[0] = 0
        else dp_m[n] = dp_Memorization(n-1) + dp_Memorization(n-2);
    }

    return dp_m[n];
}

int dp_Tabulation(int n)
{
    int dp_t[n+1]; // initialize select table
    int i;
    dp_t[0] = 0; dp_t[1] = 1;

    for(i=2; i<=n; i++)
    {
        dp_t[i] = dp_t[i-1] + dp_t[i-2];
    }

    return dp_t[n];
}

void initialize()
{
    for(int i=0;i<max; i++)
    {
        dp_m[i] = value;
    }
}



int main()
{
    initialize();

    cout<<dp_Memorization(0)<<'\n'; // 0
    cout<<dp_Memorization(1)<<'\n'; // 1
    cout<<dp_Memorization(2)<<'\n'; // 1
    cout<<dp_Memorization(3)<<'\n'; // 2
    cout<<dp_Memorization(4)<<'\n'; // 3

    cout<<dp_Tabulation(0)<<'\n'; // 0
    cout<<dp_Tabulation(1)<<'\n'; // 1
    cout<<dp_Tabulation(2)<<'\n'; // 1
    cout<<dp_Tabulation(3)<<'\n'; // 2
    cout<<dp_Tabulation(4)<<'\n'; // 3


}

<참고 자료>

https://www.youtube.com/watch?v=mmjDZGSr7EA&list=PLqM7alHXFySGbXhWx7sBJEwY2DnhDjmxm&index=1