개발기록장

동적 계획법

4 min read

용어 정의

동적 계획법 (Dynamic Programming, DP) : 주어진 문제를 부분 문제로 쪼개고, 그 부분 문제의 답을 다시 활용해서 전체의 문제를 푸는 것

활용 가능한 문제들 : 냅색, 스케줄링, 발전 계획, 편집 거리, 음성 인식 패턴 매칭, 문장 띄어쓰기, 은닉 마르코프

완화 (Relexation) : 현재 시점에서 최적값으로 지정하는 작업

// 예시 : 최소값을 찾는 문제에서의 완화
template<class T> void relex(T &a, T b){
	if(a > b) a = b;
}

전이 형식 : 완화를 진행하는 순서. 꼭짓점 u에서 v로 전이하는 변을 완화하려면 dp[u]가 확정되어 있어야 한다.

  • 끌기 전이 : 현재 a[i]의 값이 그 이전 값들을 참조.
    • ex : a[i] = a[i-1] + a[i-2]
  • 밀기 전이 : 현재 a[i]의 값을 참조해 그 뒤의 값들을 완화.
    • ex : a[i+1] = a[i] + …

예시

냅색 문제

N개의 물건에서 무게의 총합이 W를 넘지 않도록 선택했을 때, 고른 물건의 가격 총합 최댓값

  • 상황 쪼개기

    • i-1번째 상황에서 최대 가격보다 i를 골랐을 때 가격이 더 큰가?
    • i-1번째 상황에서 i를 골라도 W를 넘기지 않는가?

  • 둘 다 참이면 i번째 상황은 i-1번째 상황에서 i를 고름

  • 하나라도 거짓이면 i번째 상황은 i-1번째 상황과 동일함

  • 완화 조건 : 최댓값

// 최댓값 찾기용
template<class T> void relex(T &a, T b){
	if(a < b) a = b;
}
  • DP 테이블 생각하기
    • dp[i][w] : 무게 최대값이 w일 때, 앞에 i번째 물건까지 고를 수 있는 상황에서 가격 최대값
vector<vector<int>> dp(N+1, vector<int>(W+1, 0));
 
for(int i = 0; i < N+1; i++){
	for(int w = 0; w < W+1; w++){
		if(w - weight[i] >= 0) relex(dp[i][w], dp[i-1][w - weight[i] + value[i]);
		else relex(dp[i][w], dp[i-1][w]);
	}
}
 
return dp[N][W];

편집 거리

문자열 S, T가 있을 때 대체, 삭제, 삽입의 3가지 행동으로 S와 T를 동일하게 하려고 한다. 이 때 필요한 최소 행동 횟수를 구하시오

  • 상황 쪼개기

    • S와 T의 길이가 같음 ⇒ S에서 T와 다른 부분만큼 대체
    • S가 T보다 김 ⇒ S에서 삭제
    • T가 S보다 김 ⇒ T에서 삭제

  • 완화 조건 : 최소값

template<class T> void relex(T &a, T b){
	if(a > b) a = b;
}
  • DP 테이블 생각하기
    • dp[i][j] = S의 i번째까지, T의 j번째 까지 부분 문자열에서 최소 편집거리
vector<vector<int>> dp(S.size() + 1, vector<int>(T.size() + 1, INF));
dp[0][0] = 0;
for(int i = 0; i < S.size() + 1; i++) {
	for(int j = 0; j < T.size() + 1; j++) {
		if(i > 0 && j > 0){
			if(S[i-1] == T[j-1]) relex(dp[i][j], dp[i-1][j-1]);
			else relex(dp[i][j], dp[i-1][j-1] + 1);	
		}
		if(i > 0) {
			relex(dp[i][j], dp[i-1][j] + 1);
		}
		if(j > 0) {
			relex(dp[i][j], dp[i][j-1] + 1);
		}
	}
}

참고자료

문제 해결력을 높이는 알고리즘과 자료 구조

그래프 뷰