DP(Dynamic Programming)

동적 프로그래밍이란?

여기서 프로그래밍이란 컴퓨터 프로그래밍이라는 뜻이 아니라 테이블을 만든다는 뜻.
그리고 전혀 다이나믹하지도 않다.

(어떤 교수님은 동적 프로그래밍 = 기억하기 프로그래밍이라는 용어를 씀)
--> 이해가 확 된다!

*메모제이션도 동적 프로그래밍 중 하나.
(메모제이션이란?
  : 재귀 호출 시, 반복적으로 계산되는 것의 계산 횟수를 줄이기 위해 이전에 계산한 값을 저장해두었다가
    나중에 재사용하는 방법)

알고리즘 짤 때, *분할정복 기법 을 사용하는 경우가 있는데,
이 또한 DP.
(분할정복 기법이란?
  : 큰 문제를 한 번에 해결하기 힘들 때 작은 여러 개 문제로 나누어서 푸는 기법
    매번 재계산하지 않고, 값을 저장해두었다가 재사용하는 기법)

 

 

동적 프로그래밍의 대표적인 문제들

 

1) 막대기 자르기

정의 : 하나의 막대기를 자른다고 상상해보자. 이 때 막대기는 조각마다 가격이 다르다. 막대기를 적절하게 잘라서 가격이 가장 높도록 만들어야 한다.

 

길이별 가격

길이 (i)    0  1  2  3  4   5   6   7    8    9  10

가격 (Pi)  0  1  5  8  9  10  17  17  20  34  30

 

예 :

길이가 4인 막대기라면,

이 때 얻을 수 있는 최대 가격은 길이 2로 막대기를 두 개로 나눈 후에 5 + 5 = 10의 가격으로 만드는 것.

길이가 6이라면 최대 가격은 그냥 자르지 않고, 17이 큰 가격.

 

풀이 방법 :

길이가 n인 막대기의 최대 가격이 Rn일 때
Rn = max(Pi + Rn - i) (i는 1부터 n)

예시]
R4 = max(P1 + R3, P2 + R2, P3 + R1, P4 + R0)이다.
이때 P1 ~ P4는 이미 구해져있으므로 R3, R2, R1, R0을 구하도록 한다.
R0는 0
R1은 위의 식에서 max(P1 + R0)이므로 1
R2는 위의 식에서 max(P1 + R1, P2 + R2)에서 max(2, 5)이므로 5
R3는 위의 식에서 max(P1 + R2, P2 + R1, P3 + R0)에서 max(6, 6, 8)이므로 8 

이 과정에서 R1, R2, R3는 계속해서 나오게 되므로
이 값들을 저장하는 것.

 이 때, 
Top-down으로 불리는 메모이제이션을 사용할 수 있고,
Bottom-up으로 불리는 상향식 계산법을 사용할 수 있음.
==> 상향식 계산법이 성능이 더 좋은 경우가 많음.

 

프로그래밍 예시 :

int arr p = {0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30};

function cutRod(p, n){
	int arr Rn[100] = {0,};
    
    // Rn = max(Pi + Rn-i)에서 i는 1부터 시작하므로
    for (int i = 1; i <= n; i++){
    	int q = -1; // 각 길이에 대한 최대 가격 Ri
        for(int j = 1; j <= i; j++){
			q = Math.max(q, p[j] + r[i - 1]);
        }
        Rn[i] = q;
    }
    return Rn[n];
 }

 

 

2) 최장 공통 부분 수열(LCS) 문제

정의 : 두 개의 문자열에서 순서대로 겹치는 문자가 최대 몇 개인지 구하는 방법

 

예)

ABCDHEF

BCDEF

두 개의 문자열에서

 

   1) 공통 부분 문자열은

      ABCDHEF

      BCDEF

 

   2) 공통 부분 수열은

      ABCDHEF

      BCDEF

 

 

계산식 :

 

 

간단한 이해를 위한 프로그래밍 예시 :

for (int i = 1; i <= A.length; i++) { 
	for (int j = 1; j <= B.length; j++) { 
		if (A[i - 1] == B[j - 1]) { 
			LCS[i][j] = LCS[i - 1][j - 1] + 1; 
			if (ans < LCS[i][j]) { 
				ans = LCS[i][j]; 
			} 
		} 
	} 
}

// 출처: https://mygumi.tistory.com/126 [마이구미의 HelloWorld]

 

 

 

3) 피보나치 수열

정의 : 수열의 n번째 위치에서 앞의 두 수를 더한 값이 위치하는 수열 (첫번째와 두번째는 0과 1이다.) [1, 1, 2, 3, 5, 8 .....]

 

프로그래밍 예시 : 

fuction fn(n){
	if (n == 0){
    	return 1;
    }else if(n == 1){
    	return 1;
    }else{
    	return fn(n - 1) + fn(n - 2);
    }

 

문제점 :

fn(5);
fn(4) + fn(3);
fn(3) + fn(2) + fn(2) + fn(1)
fn(2) + fn(1) + fn(1) + fn(0) + fn(1) + fn(0) + fn(1)

으로 fn(2)의 계산이 반복됨.

따라서 숫자가 커질수록 이러한 반복 계산이 많아짐.

 

여기서 적용할 수 있는 것이 DP

 

DP는 이미 계산한 문제는 재사용할 수 있기 때문에 반복해서 계산하지 않아도 된다.

// 함수의 계산 결과를 저장할 수 있는 객체를 생성한다.
int arr[100] = {0,};

arr[0] = 1;
arr[1] = 1;

// 이를 이용해 피보나치 수열 구하기.
function fn(n){
	if(!arr[n]){
    	arr[n] = fn(n - 1) + fn(n - 2);
    }
    return arr[n];
}

 

 

4) 거스름돈 문제

도 동적 프로그래밍인줄...ㅎ 거스름돈 알고리즘은 대표적인 그리디 알고리즘

동적 프로그래밍
Dynamic Programming은 전체 문제를 여러 개의 하위 문제로 나누어 풀고, 하위 문제들의 해결 방법들을 결합하여 최종 문제를 해결하는 문제 해결 방식이다.

그리디 알고리즘
Greedy Algorithm은 문제를 해결하는 과정에서 그 순간순간마다 최적이라고 생각되는 결정을 하는 방식으로 진행하여 최종 해답에 도달하는 문제 해결 방식이다.

 

 

 

1) 피보나치 수열 / 그리디 알고리즘 개념 참고

 

동적 계획법(Dynamic Programming)과 탐욕법(Greedy Algorithm)

 

2) 최장 공통 부분 수열 문제  참고

LCS(최장 공통 부분 수열) 알고리즘 :: 마이구미

 

3) DP 개념과 문제 참고

(Algorithm) 동적 프로그래밍(Dynamic programming) - 배낭 문제, LCS 문제, 막대기 문제

 

4) DP 개념