13. DP (충남대 알고리즘 강의록)

충남대학교 컴퓨터공학과 이영석 교수님의 "알고리즘" 강의 실습 내용입니다.

• 실습 문제들의 코드 위주로 구성되어 있습니다.

문제 1: 피보나치 수열 §

/**
 * CNU week13 prob1
 *
 * Fibonacci
 */
 
#include <iostream>
#include <vector>
 
using namespace std;
 
// 정수 오버플로우를 방지하기 위함
#define uint uint64_t
 
int main() {
	int N;
	cin >> N;
	
	// 모든 숫자를 0으로 초기화
	vector<uint> cache(N + 1, 0);
	
	// Fibonacci(1) = 1이므로
	cache[1] = 1;
	
	// Fibonacci(N)까지를 점화식을 이용해 계산함
	for (int i = 2; i <= N; i++) {
		cache[i] = cache[i - 1] + cache[i - 2];
	}
	
	// STDOUT
	cout << cache[N] << endl;
	
	return 0;
}

문제 2: 배낭 §

/**
 * CNU week13 prob2
 *
 * Knapsack
 */
 
#include <iostream>
#include <vector>
 
using namespace std;
 
int main() {
	int C, N;
	cin >> C >> N;
	
	// 물품의 무게를 1-index로 저장함
	vector<int> W(N + 1, 0);
	for(int i = 1; i <= N; i++) {
		cin >> W[i];
	}
 
	// 물품의 가치를 1-index로 저장함
	vector<int> V(N + 1, 0);
	for(int i = 1; i <= N; i++) {
		cin >> V[i];
	}
	
	// cache[i번째 물품][무게제한 w] == 1번째 ~ i번째 물품까지 고려했을때 무게제한 w내에서의 최대 가치
	vector<vector<int>> cache(N + 1, vector<int>(C + 1));
 
	// 모든 물품 범위와 무게제한에 대해 최대 가치를 저장함
	for(int i = 1; i <= N; i++) {
		for(int w = 1; w <= C; w++) {
 
			// 만약 물품 범위의 마지막 물품의 무게가 현재 무게제한보다 클 경우
			if(W[i] > w) {
 
				// 물품 범위의 마지막 물품을 가방에 넣지 않음
				cache[i][w] = cache[i - 1][w];
 
			// 만약 물품 범위의 마지막 물품의 무게가 현재 무게제한보다 작거나 같을 경우
			} else {
 
				// 마지막 물품을 가방에 넣었을때와 넣지 않았을때 중 가치가 큰것을 고름
				cache[i][w] = max(V[i] + cache[i - 1][w - W[i]], cache[i - 1][w]);
			}
		}
	}
	
	// 주어진 물품 범위와 무게 제한에 대한 가치의 최고값 출력
	cout << cache[N][C] << endl;
	return 0;
}

문제 3: 최장공통부분수열 §

/**
 * CNU week13 prob3
 *
 * Longest Common Subsequence
 */
 
#include <iostream>
#include <vector>
 
using namespace std;
 
int main() {
	string s1, s2;
	cin >> s1 >> s2;
 
	int N1, N2;
	N1 = s1.size();
	N2 = s2.size();
 
	// cache[첫번째 문자열의 1-index i1][두번째 문자열의 1-index i2] ==
	//	  첫번째 문자열의 1 ~ i1의 범위와
	//	  두번째 문자열의 1 ~ i2의 범위를 고려한 LCS
	vector<vector<int>> cache(N1 + 1, vector<int>(N2 + 1, 0));
 
	// 모든 i1와 i2의 범위 조합에 대해 계산함
	for(int i1 = 1; i1 <= N1; i1++) {
		for(int i2 = 1; i2 <= N2; i2++) {
 
			// 만일 0-index로 변환한 i1의 문자와 i2의 문자가 같을 경우
			//   지금까지 이어져오던 LCS에 현재의 문자를 추가해야됨
			//	  지금까지 이어져오던 LCS Stream은 현재의 동일한 두 문자를 제외한 이전의 범위의 LCS Stream이다
			//	  따라서, 문자열 s1에 대한 1 ~ (i1 - 1)의 범위와
			//	  문자열 s2에 대한 1 ~ (i2 - 1)의 범위에서의 LCS길이에 1을 추가한 값이
			//	  1 ~ i1과 1 ~ i2의 범위에 대한 LCS의 길이가 됨
			if(s1[i1 - 1] == s2[i2 - 1]) {
				cache[i1][i2] = cache[i1 - 1][i2 - 1] + 1;
 
			// 만일 두 문자가 같지 않은 경우
			//	  두 문자 각각을 제외했을때의 LCS 중 가장 긴것을 선택
			} else {
				cache[i1][i2] = max(cache[i1 - 1][i2], cache[i1][i2 - 1]);
			}
		}
	}
 
	cout << cache[N1][N2] << endl;
	return 0;
}