#5 동적 계획법 (DP)

동적 계획법(Dynamic Programming)

1) 큰 문제를 작은 부분 문제들로 나누어 푸는 방법

2) 점화식 세우기

3) 메모이제이션(Memoization) 기법 사용

 

ex) 피보나치 수열

[1, 1, 2, 3, 5, 8, 13, 21, 34, ....]

F(n) = F(n-1) + F(n-2)

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

n = 6

다음과 같은 피보나치 수열을 수행하는데 재귀적으로 이루어지면서 중복되는 함수가 많습니다.

예를 들어 n이 6일때 피보나치 수행도를 보면 F(3)이 3번이나 수행되었습니다. F(3)의 값은 1번만 알면되는데

재귀적으로 탐색하는 과정에서 중복적으로 계산된 것입니다.

이를 방지하고자 메모이제이션 기법을 사용합니다.

 

메모이제이션(Memoization)

부분문제를 계산한 결과를 메모리에 저장

동일한 계산을 할 때 이전에 메모리에 저장한 값을 이용

배열 사용

n = 6

메모이제이션을 사용했을 경우 중복되는게 사라집니다.

using namespace std;
using ll = long long;
using ull = unsigned long long;
int dp[10001];
int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    for (int i = 0; i <= 10000; i++)dp[i] = -1;
 
    memset(dp, -1, sizeof(dp)); //cstring
 
    fill(dp, dp + 10001, -1);//배열인 경우
    fill(v.begin(), v.end(), -1);//벡터인 경우
 
    return 0;
}

dp배열을 만들기 전에 미리 초기화를 해주어야 하는데 초기화 방법에는 총 3가지가있습니다.

1) 일반적인 for문으로 모든 배열의 값을 초기화

2) memset 초기화 : 메모리 형태가 unsigned char이므로 0~255인 수로 초기화 할시 사용합니다. (-1, 0)으로 초기화할                              시   사용

                          #include<cstring> 에 존재합니다.

3) fill 초기화 : 첫번째 인자는 포함, 두번째 인자는 포함하기 전 입니다.

int fibo(int n) {
    if (dp[n] != 1)return dp[n]; //이미 계산된 값은 바로 리턴
    if (n <= 1) {//n이 0과 1일때 설정
        dp[n] = n; //dp[0] =0, dp[1] = 1
        return dp[n];
    }
    else {
        dp[n] = fibo(n - 1) + fibo(n - 2);
        return dp[n];
    }
}

---

<Top-Down>                                                      VS                <Bottom-Up>

재귀 호출 이용                                                                        반복문 이용

큰 문제에서 필요한 부분 문제들을 호출해나가는 방식                      제일 작은 부분문제부터 답을 구해가는 방식

ex) F(n) = F(n-1) + F(n-2)                                                          ex) k = 1, 2, .....~n

상대적으로 DP식을 이해하기 쉽다                                               상대적으로 메모리 시간이 작다

시간복잡도 : DP Table의 크기(배열) * 한 칸을 계산하는데 걸리는 시간 시간복잡도 : 반복문의 연산 횟수

 

<Top-Down>

int fibo(int n) {
    if (dp[n] != 1)return dp[n]; //이미 계산된 값은 바로 리턴
    if (n <= 1) {//n이 0과 1일때 설정
        dp[n] = n; //dp[0] =0, dp[1] = 1
        return dp[n];
    }
    else {
        dp[n] = fibo(n - 1) + fibo(n - 2);
        return dp[n];
    }
}

<Bottom-Up>

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

다른 방법으로 뿌려주는 방법이 있습니다.

dp[1] = 1;
    for (int i = 1; i <= 10000; i++) {
        dp[i + 1] += dp[i];
        dp[i + 2] += dp[i];
    }

뿌려주는 방법이 좋을때가 많습니다.

---

DP Tips

1) 참조형 변수 (Reference variable)

   [자료형]&[참조 변수명] = [변수명]      ex) int &a = b;

2) When use DP?

계속 중복이 일어나는 경우 

O(N!) (ex 일렬로 나열하기) 

O(2^N) (ex 모든 부분집합 고려)

 

최대/최소, 경우의 수

 

3) How to use DP?

1. Naive 하게 계산 -> 중복이 발생하는가? 체크

2. 중복이 발생한 경우 DP로 해결가능한 문제인지 파악 (ex 부분문제로 나뉘어 지는가?)

3. DP tabl로 상태(status) 표현  ex dp[a][b] 등등

4. 상태(status) 간의 관계식 구하기 (점화식 구하기) ex f(n) = f(n-1) + f(n-2)

5. Top-Down or Bottom-Up and Base case(ex f(0) = 0, f(1) = 1) 설정 

 

Prefix Sum (누적합)

i번째 원소부터 j번째 원소까지의 합

psum[i] = 1번째 원소부터 i번째 원소까지의 합

psum[i] = psum[i-1] + arr[i]

arr[i] + arr[i+1] + arr[i+2] + .....+ arr[j] = psum[j] - psum[i-1]