[C++] 동적 계획법 Dynamic Programming(DP) 사용법

안녕하세요 뚜디 입니다:)

< 동적 계획법 Dynamic Programming (DP) >

---

1. 동적 계획법이란?

2. 동적 계획법 사용

3. 동적 계획법 예시

---

1. 동적 계획법이란?

다이나믹 프로그래밍(Dynamic Programmin)은 프로그래밍 대회(코테)를 준비하시는 분들에게는 반드시 숙지해야할 알고리즘중 하나입니다. 다이나믹 프로그래밍 문제는 종류가 많고, 컴퓨터적인 사고력을 판단하기에 적합하다는 점에서 많이 출제되기 때문입니다.

다이나믹 프로그래밍(Dynamic Programmin)이란?
"하나의 문제는 단 한번만 풀도록 매번 저장하는 알고리즘" 다시 그 문제를 요구 할 때 기존에 이미 저장해 두었던값을 가져온다. 여러개의 하위 문제(분할 정복 기법)들로 나누어 문제들을 처리 할 때 사용할 수 있다.

 

2. 동적 계획법 사용

🔶 동적 계획법을 사용할 수 있는 가정
  1. 피보나치 수열
  2. 큰 문제들이 작은 문제들로 이루어진 문제, 작은 문제들로 분할 가능
  3. 단, 큰 문제와 작은 문제의 관계에서 사이클이 발생해선 안된다.
🔶 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 활용된다.
  1. 점화식을 세울 수 있어야 한다.(피보나치)
  2. 5를 구하는 과정에서 이전에 저장했던 1,2,3,4를 6을 구하는 과정에서도 사용할수 있는 문제여야한다.

분할 정복 예시(피보나치 수열)

동적 계획법의 사용을 알아보기전에 분할 정복을 먼저 살펴보며, 동적 계획법이 왜 필요한지 알아보도록 합니다..
상당수의 분할 정복 기법(재귀적 성격)은 동일한 문제를 추후 다시 푼다는 단점을 가지고 있다.

가장 대표적인 예시인 피보나치 수열을 예시로 들어보도록 하겠습니다.

피보나치 수열 점화식

#include <iostream>

int solution(int x) {
	if (x == 0) return 0;
    if (x == 1) return 1;
    if (x == 2) return 1;
    return solution(x - 1) + solution(x - 2);
}

int main() {
	cout << solution(10) << endl;
    return 0;
}

피보나치 수열을 재귀함수로 소스코드하게되면 위와 같이 구현을 할 수 있습니다.
위 경우 10을 입력 할 때, 답은 55로 잘 출력되는 것을 확인 할 수 있지만,
50을 입력하여 F(100)의 피보나치 수열을 구하려고 한다면 어떤 결과를 출력하는지 확인해봅시다.

#include <iostream>

int solution(int x) {
	if (x == 0) return 0;
    if (x == 1) return 1;
    if (x == 2) return 1;
    return solution(x - 1) + solution(x - 2);
}

int main() {
	cout << solution(100) << endl;
    return 0;
}

100을 입력하여 실행을 해보면 실행이 되지않고 Error가 발생하게됩니다.
이때, 디버그를 통해 CPU를 살펴보게 되면 CPU가 무한적으로 증가하시는것을 보실수있습니다.

그 이유는 피보나치 수열이 1개만 늘어나도 계산량은 2배가 늘어나기 때문인데,
간단하게 생각하면 F(100)은 2의 100제곱으로 처리할수 없을 정도의 계산량이 입력되기 때문입니다.

그래서 이를 해결하기 위해 동적 계획법(DP)를 활용하시면 됩니다.

 

3-1. 동적 계획법 예시 (피보나치 수열)

#include <iostream>
#include <vector>

vector<int> dp;

int solution(int x) {
	if (x == 0) return 0;
   	if (x == 1) return 1;
    	if (x == 2) return 1;
   	if (dp[x] != -1) return dp[x]; //dp에 값이 있다면 바로 리턴(이미 구해짐)
    dp[x] = solution(x - 1) + solution(x - 2);
    return dp[x];
}

int main() {
	int n;
    	cin >> n;
	dp.resize(n + 1, -1); //vector dp 초기화 : 초기값은 -1
	cout << solution(n) << endl;
    return 0;
}

1. 벡터 dp를 추가하여 문제의 값을 저장한다.
  => 배열로 해도 문제없다. 단, resize와 초기화가 간편한 벡터를 추천
2. 벡터 dp에 저장된 값을 이용하여 한번 계산된 문제의 값은 다시 계산하지 않도록 바로 리턴한다.

1,2번 과정을 추가했을뿐인데, 한번 계산한 값은 다시 계산할 필요가 없기 때문에 O(N)가 상승하게 된다.
단, 이 기법은 별도의 메모리를 사용해야하는 단점도 있다.

 

3-2. 동적 계획법 예시 (막대기 자르기)

• 문제 설명

막대기 길이가 [0, 1, 2, 3, 4] 이고 각각 막대기의 가격이 [0, 1, 5, 8, 9] 일 때, 길이가 4 인 막대기를 자를 때 얻을 수 있는 최대 가격은?

  ● 막대기 길이가 4 일 때의 최고 가격
     ○ 자르지 않고 그냥 4 길이인 막대기
        - 막대기 길이가 0 일 때의 최고 가격 + 막대기4 가격
     ○ [1, 3] 으로 두 개로 자른 막대기
        - 막대기 길이가 1 일 때의 최고 가격 + 막대기3 가격
        - 막대기 길이가 3 일 때의 최고 가격 + 막대기1 가격
     ○ [2, 2] 으로 두 개로 자른 막대기
        - 막대기 길이가 2 일 때의 최고 가격 + 막대기2 가격

• 문제 풀이

🔶 점화식을 세운다.
 - Mi를 i길이인 막대기의 최고 가격이라고 하고 Ni를 i길이인 막대기의 가격이라고 할때,
 M4 = max[N1 + M3, N2 + M2, N3 + M1, N4 + M0]로 점화식을 세울 수 있다.
 막대기ㅣ 길이가 4일 때의 최고 가격은 막대기 길이가 3일 때의 최고 가격도 똑같이 재귀적으로 구한다.
 단, DP 기법을 사용하여 똑같은 계산은 반복하지 않도록 벡터에 저장한다.

M[1] = max[N[1] + M[0]]
M[2] = max[N[2] + M[0], N[1] + M[1]]
M[3] = max[N[3] + M[0], N[2] + M[1], N[1] + M[2]]
M[4] = max[N[4] + M[0], N[3] + M[1], N[2] + M[2], N[1] + M[3]]

int dp(vector<int> N, x)
{
    vector<int> M(x);
    
    for (int i = 0; i < x; i++)
    {
        int temp = -1;
        for (int j = 0; j < i; j++)
        {
            temp = max(temp, N[i] + M[j - i]);
        }
        M[i] = temp;
    }

    return M[x];
}