03. 동적 계획법

[1. 개요]

큰 의미에서 분할 정복과 같은 접근 방식

그러나 하나의 문제의 답을 여러번 계산하는 대신 한 번만 계산하고

계산 결과를 재활용함

 

두 번 이상 계산되는 부분 문제를 중복되는 부분문제라고 한다.

 

계산의 중복 횟수는 분할의 깊이가 깊어질 수록 지수적을 증가한다.

(같은 값을 두번 이상 계산할 일이 빈번해질 수 있다.)

 

한 번 계산한 값을 저장해두었다가 재활용하는 최적화 기법을 메모이제이션이라 한다.

 

보통 동적 계획법 알고리즘 구현은 아래와 같은 두 단계로 구성

1. 문제를 완전 탐색을 이용해 해결
2. 중복되는 부분 문제를 한번만 계산하도록 메모이제이션을 적용

 

 

 

[2. 메모이제이션]

수학의 함수와 프로그래밍에서 함수는 사실 서로 다르다

프로그래밍을 할 때는 함수의 불변성이 성립하지 않을 수 있기 때문이다.

(전역 변수, 입력 파일... 과 같은 수 많은 입력에 의해 작동하기 때문.)

 

참조적 투명성

함수의 반환 값이 그 입력 값만으로 결정되는지의 여부

 

참조적 투명성 함수

입력이 고정되어 있을 때 그 결과가 항상 같은 함수

 

== 구현 패턴 (작성을 일관되게 하는 것이 좋다.) ==

1. 기저 사례를 제일 먼저 처리
   => 입력이 범위를 벗어난 경우 등...
   
   
2. cache[] 를 모두 -1로 초기화 
   => memset() 는 1byte 단위로 초기화 하기 때문
   => -1 은 아직 계산되지 않음을 의미
   => 반환 값이 음수일 수 있다면 무효함.
   
   
3. ret 값은 cache[a] 에 대한 참조형
   => cache 가 다차원배열일 때 유용하다.
   => 배열의 인덱싱 실수를 줄일 수 있다.
   
   

 

[3. 메모이제이션 시간복잡도]

(존재하는 부분 문제의 수) X (한 부분 문제를 풀 때 필요한 반복문의 수행 횟수)

=> 예시 (이항계수 계산)

=> 부분 문제의 수는 O(n^2)

=> 부분 문제를 계산 할 때 필요한 반복문은 없으니 O(1) 

=> 이항 계수를 동적 계획법으로 풀이 시 시간 복잡도 == O(n^2)

 

 

 

[4. 최적화 문제]

여러 개의 가능한 답 중 가장 좋은 답을 찾는 문제

 

최적화 문제에 특정 성질이 성립할 경우,

단순한 메모이제이션을 넘어

좀 더 효율적인 동적 계획법을 구현 할 수 있다.

 

최적 부분 구조

어떤 문제와 분할 방식에 성립하는 조건

각 부분 문제의 최적해만 있으면, 전체 문제의 최적해를 쉽게 얻어 낼 수 있는 경우

 

 

예시)

최대 증가 부분 수열

	#include <iostream>
	#include <vector>
	#include <algorithm>
	// 완전탐색 풀이
	int lis(const std::vector<int> &A)
	{
	// 기저 사례
	if (A.empty()) {
	return 0;
	}
	int ret = 0;
	for (int i = 0; i < A.size(); i++) {
	std::vector<int> B;
	// i 번째 원소는 선택하였으므로
	// i+1 번째 이후부터 i번째 원소보다 큰 값만 추출
	for (int j = i+1; j < A.size(); j++) {
	if (A[i] < A[j]) {
	B.push_back(A[j]);
	}
	}
	// 1은 i번째 원소를 선택하여
	ret = std::max(ret, 1 + lis(B));
	}
	return ret;
	}
	// 동적계획법 풀이
	int n;
	int cache[101], S[100];
	// 수열이 start 부터 시작한다.
	// -1 부터 시작하는 경우는 아예 처음부터 시작하는 경우
	//
	// start 부터 시작하는 부분 증가 수열 중 최대 길이를 반환한다.
	int lis2(int start)
	{
	// 캐시를 먼저 확인
	int &ret = cache[start+1];
	if (ret != -1) {
	return ret;
	}
	ret = 0;
	for (int next = start+1; next < n; next++) {
	if (start == -1 || S[start] < S[next]) {
	ret = std::max(ret, 1 + lis2(next));
	}
	}
	return ret;
	}

view raw lis.cpp hosted with ❤ by GitHub

 

 

[5. 기타 예제들]

 

 

 

=> 완전탐색으로도 시간내에 풀린다함

=> 답안을 정렬해서 출력?

	#include <iostream>
	#include <string>
	#include <algorithm>
	#include <cstring>
	#include <vector>
	std::string W, S;
	int cache[101][101];
	bool matchMemoized(int w, int s)
	{
	int &ret = cache[w][s];
	if (ret != -1) {
	return ret;
	}
	// '*' 를 찾는 과정
	while (s < S.size() && w < W.size() &&
	(W[w] == '?' || W[w] == S[s])) {
	w++;
	s++;
	}
	if (w == W.size()) {
	ret = (s == S.size());
	return ret;
	}
	if (W[w] == '*') {
	for (int skip=0; s+skip <= S.size(); skip++) {
	if (matchMemoized(w+1, s+skip)) {
	ret = 1;
	return ret;
	}
	}
	}
	ret = 0;
	return ret;
	}
	int main()
	{
	int C;
	char wildcard[101];
	char str[101];
	scanf("%d", &C);
	for ( ;C > 0; C--) {
	std::vector<std::string> answer;
	scanf("%s\n", wildcard);
	W = wildcard;
	int count;
	scanf("%d", &count);
	for (int i=0; i<count; i++) {
	memset(cache, -1, sizeof(cache));
	scanf("%s\n", str);
	S = str;
	if (matchMemoized(0, 0)) {
	answer.push_back(S);
	}
	}
	// 매칭되는 것들을 정렬해서 출력해야 한다?
	std::sort(answer.begin(), answer.end());
	for (const std::string &ret : answer) {
	printf("%s\n", ret.data());
	}
	}
	return 0;
	}

view raw wildcard.cpp hosted with ❤ by GitHub