c++ DP

작은 범위에서의 결과를 더 큰 범위의 계산에 사용한다.

처음부터 차근차근 계산 값을 저장하면서 확장하여 목적지 까지 도달하는 기법.

보통 점화식이 존재한다.

 

예) 출발지에서 도착지 까지 갈 수 있는 경우의 수.  P[i, j] = P[i-1, j] + P[i, j-1]

출발 (1)	1	1
1	2	3
1	3	도착 (6)

 

 

활용 예제  [0/1 배낭 채우기]

배낭 용량 : 50kg

보석 정보:

가치	무게
60	10kg
100	20kg
120	30kg

보석은 자를 수 없고, 최대로 담을 수 있는 가치 값을 구하기.

 

 

[공략]

<처음 부터 차근차근 채워가며 각 채워진 값은 항상 최적의 해다.>

1. 보석 0부터 i 번째 까지 고려, 무게 0부터 w 까지의 총 가치를 나타내는 2차원 배열 생성.

i \ w	0	1	2	...	50
0	0	0	0	0	0
1	0	?	?	?	?
2	0	?	?	?	?
3	0	?	?	?	?

2. 보석이 0개(0번째) 거나 무게(w)가 0일 땐, 가방에 아무것도 없다. 따라서 0.

3. i 번째 보석의 무게(wi) 가 현재 가방무게(w) 보다 크면 못 넣으니, i-1개의 보석만으로 최대 가치값을 계산했던 전 단계의
   값을 가져와 저장한다.

4. 보석의 무게가 가방무게보다 작으면 넣을 수 있으니 경우를 따진다.  둘 중 큰 것을 저장한다.
  (i번째 보석을 위해, i번째 보석만큼의 무게를 비웠을 때의 최적값 + i번째 보석의 가격) vs

  (i-1개의 보석들을 가지고 구한 전 단계의 최적값 중 큰 것을 선택)

4. 2차원 배열의 마지막 요소를 출력한다.

 

    int totalW = 50;	//가방 무게
    vector<pair<int, int>> juwel{ {60,10},{100,20},{120,30} };    //가치, 무게
    vector<vector<int>> m(juwel.size() + 1, vector<int>(totalW + 1, 0));    
   
    //i번째 물건까지 고려한 현재 가방 무게(w)에 따른 총 가치의 합//
    
    for (int i = 1; i < DP.size(); ++i)         //보석 갯수
    {
        for (int w = 1; w <= totalW; ++w)       //가방 무게
        {
            int jweight = juwel[i - 1].second;  //현재 보석 정보
            int jvalue = juwel[i - 1].first;

            if (jweight > w)
                DP[i][w] = DP[i - 1][w];
            else
            {
                DP[i][w] = max(DP[i - 1][w], DP[i - 1][w - jweight] + jvalue);
            }
        }
    }


    cout << "배낭에 넣을 수 있는 최대 가치 : " << DP[DP.size() - 1][totalW] << endl;

 

 

 

활용 예제 [최장 공통 부분 수열]

두 문자열에서 각각 처음 부터 차례대로 확인했을때 공통적으로 존재하는 글자들의 집합을 구하기.

A = "ABCDEF"
B = "GBCDFE"

DP 테이블

 

[공략]

1. 첫 빈공간을 더한 문자열 각각의 문자를 확인하는 2차원 int 배열 생성. (첫 빈공간의 행과 열은 0)

2. 2중 for문으로 각각의 문자들을 전부 비교한다. (i, j)
   2-1. i 번째 A와 j번째 B가 같으면   [i-1][j-1] +1 의 값을 저장.
   2-2. 같지 않으면 [i-1][j]  와  [i][j-1] 중 큰 것을 저장.

3. 2차원 배열의 마지막 요소는 최장 공통 부분 수열의 크기

4. 마지막 요소부터 시작하여 위 or 왼쪽로 둘중에 하나가 같으면 그곳으로 이동, 둘 다 다르면 현재 요소의 글자를 저장
    하면서 대각선(i-1, j-1)으로 이동

   4-1. i 또는 j 가 0이면 종료.

 

 

    string A = "ABCDEF", B = "GBCDFE";
    vector<vector<int>> Map(A.length() + 1, vector<int>(B.length() + 1, 0));

    for (int i = 1; i < Map.size(); ++i)    //A 글자
    {
        for (int j = 1; j < Map[0].size(); ++j) //B 글자
        {
            if (A[i - 1] == B[j - 1])
                Map[i][j] = Map[i - 1][j - 1]+1;
            else
                Map[i][j] = max(Map[i][j - 1], Map[i - 1][j]);
        }
    }
    cout << "최장 공통 부분 수열 크기 : " << Map[Map.size() - 1][Map[0].size() - 1] << endl;

    int i = Map.size() - 1, j = Map[0].size() - 1;
    string commonstr;
    while (i >= 1 && j >= 1)
    {
        if (Map[i][j] == Map[i][j - 1])
            --j;
        else if (Map[i][j] == Map[i - 1][j])
            --i;
        else
        {
            commonstr = A[i - 1] + commonstr;
            --i; --j;
        }
    }
    cout << "부분수열 : " << commonstr << endl;