4. DP Technique - 최적화 문제의 실제 답 계산하기

이전까지는 다이나믹 프로그래밍 알고리즘을 사용하여 최적화 문제를 풀 때 최적해의 점수만을 계산했다.

가장 긴 증가 부분 수열을 대신 수열의 길이를 찾고, 양자화한 결과 수열 대신 오차 제곱의 합을 구했다.

만약 최적해를 직접 구해야 한다면 어떻게 해결해야 할까?

예제 - 최대 증가 부분 수열 실제로 출력하기

이전에 풀었던 LIS 문제에서 LIS의 길이 대신 LIS를 구성하는 원소를 구해보자.

가장 먼저 떠오르는 방법은 LIS의 길이를 구하는 재귀함수에서 lis의 길이 대신 실제 LIS의 원소들을 반환하도록 하는 것이다.

그런데 이는 구현하기 복잡할 뿐만 아니라 느리고 메모리를 많이 차지한다는 단점이 있다.

그렇다면 재귀함수의 부분문제에서 첫번째 원소를 반복문으로 돌려가며 고를 때 LIS의 길이가 최대가 되는 원소를 기록해 두도록 한다.

코드로 구현하면 다음과 같이 할 수 있다.

// 최대 증가 부분 수열을 실제로 구하는 다이나믹 프로그래밍 알고리즘

int n;

int cache[101];

int S[100];

int choices[101];  // LIS의 길이가 최대가 되는 원소를 저장하는 배열

int lis(int start){

int& ret = cache[start];

if(ret != -1) return ret;

ret = 1;

int bestNext = -1;

for(int next = start+1; next < n; next++){

if(start == -1 || S[start] < S[next]){

int cand = lis(next) + 1;

if(cand > ret) {

ret = cand;

bestNext = next;  // 최대가 되는 원소 기록

}

}

}

choices[start+1] = bestNext;

return ret;

}

최적화 문제 답 계산하기 레시피

1. 재귀 호출의 각 단계에서 최적해를 만들었던 선택을 별도의 배열에 저장해둔다.

2. 별도의 재귀함수를 이용해 이 선택을 따라가며 각 선택지를 저장하거나 출력한다.