동적 계획법 Dynamic Programming (+ LIS)

 DP의 정의는 '복잡한 문제를 간단한 문제로 나누어 풀고, 이 subproblem으로 원 문제를 푸는 것'이다. 어떻게 보면 divide-and-conquer과 유사하지만, DP의 경우 subproblem이 중복되기 때문에 좀 더 빠른 시간으로 풀 수 있다.

 

 그렇기 때문에 필자는 DP의 핵심이 memoization과 recursion relation(점화식)의 2가지라 생각한다. memoization으로 이미 계산 한 값이라면 그 값을 return하고, recursion relation으로 계산한 값을 이용해 다음 값을 빠르게 구할 수 있다.

 

예제 : 냅색

if j - cost[i] >= 0 then dp[i][j] = max(dp[i][j], dp[i-1][j-cost[i]] + value[i])

else dp[i][j] = dp[i-1][j]

 

예제 : LIS 문제

2^n

n^2(DP)

nlogn

nlogn + 추적

 2개의 vector를 사용해서 LIS 추적을 할 수 있다. 기본적으로 LIS의 길이를 알아내는 LIS 배열, 그리고 arr[i]가 IS의 마지막 element일 때 LIS 길이를 저장할 dp 배열. 이렇게 2개를 둔다. 기본적인 알고리즘은 LIS의 길이를 구할 때와 동일하다. 다만 달라진 것은 input array의 element를 탐색 할 때 그 element를 마지막으로 가지는 LIS의 길이를 dp 배열에 저장한다. 그렇게 하면 arr에 따른 dp 배열이 저장된다. dp 배열을 역순으로 숫자가 1 감소하는 것들만 모아 탐색하면 결과가 나온다!

void getLIS() { // nlogn에 LIS + 추적
	int N; cin>>N;
	vector<int> arr(N), LIS, dp(N, 0);
	// arr : 입력 vector
	// LIS : LIS의 길이를 구할 vector
	// dp : arr[i]가 마지막 element일 때, LIS의 max length vector
	for(int i = 0; i<N; i++){
		cin>>arr[i];
	}

	LIS.push_back(arr[0]);
	dp[0] = 1;
	for(int i = 1; i<N; i++){
		if(LIS.back() < arr[i]){ // LIS를 늘일 수 있는 경우
			LIS.push_back(arr[i]); // LIS 배열 제일 뒤에 해당 값을 넣고
			dp[i] = LIS.size(); // dp는 해당 값으로 넣음
		}
		else{ // LIS 중간에 넣는 경우
			int idx = lower_bound(LIS.begin(), LIS.end(), arr[i]) - LIS.begin(); // 넣을 위치 찾고
			LIS[idx] =arr[i]; // 해당 값 갱신()
			dp[i] = idx + 1; // arr[i]를 마지막으로 가지는 LIS의 max length : idx + 1
		}
	}

	int answer = LIS.size();
	cout<<answer<<'\n';
	stack<int> stk;
	for(int i = N-1; i>=0; i--){ // dp 배열에서 뒤에서부터 가져옴
		if(dp[i] == answer){
			stk.push(arr[i]);
			answer--;
		}
	}

	while(!stk.empty()){
		cout<<stk.top()<<' ';
		stk.pop();
	}
}

 

DP 문제들의 경우 점화식을 잘 도출해야 한다. 직관적으로 뽑아낼 수 있다면 좋겠지만 그렇지 못할 경우에는 small case부터 하나하나 올려가면서 어떻게 다음 수치가 나오는지를 생각해 보자.