[알고리즘] DP(Dynamic Programming)

오늘은 알고리즘의 주요 유형 중 하나인 DP에 대해 정리해보려고 한다.

이제 새로운 한해가 되었으니 차곡차곡 블로그를 써보려고 한다!!

 

1. 개념

DP란 무엇인가.. Dynamic Programming이다. 한국말로 하면 동적 계획법이다. 이게 뭐냐해서 공부를 해봤다. 

DP는 문제의 입력사례를 분할하여 문제를 푼다는 점에서 분할 정복과 비슷하다. 

 가장 기본적인 개념은 큰 문제를 작은 문제로 쪼개서 그 답을 저장해두고 재활용하는 것이다. 그래서 이 동적 계획의 개발 절차를 책으로 찾아보니까...

 

1. 문제의 입력사례에 대해서 해답을 계산하는 재귀 관계식(recursive property)을 세운다.

2. 작은 입력사례부터 먼저 해결하는 상향식 방법으로 전체 입력사례에 대한 해답을 구한다.

 

- 이렇게 아주 딱딱하게 적혀있다. 무슨 말인지 알 것 같기도 하지만, 쉬워보이진 않는다. 이제 제대로 DP에 대해서 알아보자!

 

2. 사용하는 이유

우리가 흔히 아는 재귀 방식, 그러니까 return F[n] = F[n-1] + F[n-2] 이러한 형식의 재귀는 성능면에서도 그렇고, 작은 문제들이 발생할 경우가 크다. 그래서 성능을 효율적으로 향상시키기 위해서 이 DP를 사용한다고 할 수 있다.

 

Ex) 분할정복으로 이항계수 구하기

int bin(int n, int k)
{
	if(k == 0 || n == k)
    	return 1;
    else
    	return bin(n-1, k-1) + bin(n-1, k);
}

-> 재귀를 호출할 때마다 같은 사례를 중복 계산한다 => 비효율적!

 

Ex) 동적계획으로 이항계수 구하기

int bin2(int n, int k)
{
	index i, j
    int B[n][k];
    
    for(i = 0; i <= n; i++)
    {
    	for(j = 0; j <= minimum(i, k); i++)
        {
        	if(j == 0 || j == i)
            	B[i][j] = 1;
            else
            	B[i][j] = B[i-1][j-1] + B[i-1][j];
    	}
    }
    
    return B[n][k];
}

 

훨씬 성능이 좋아진 모습이다.

 

3.  문제 풀기

① DP로 푸는 문제인지 판단

- a. 겹치는 부분 문제(Overlapping Subproblem)

 동일한 작은 문제들을 반복해서 나타나는 경우 DP 사용하여 문제 풀이 가능

 동일한 문제들이 반복해야 Memoization 이용함

 

- b. 최적의 부분 구조(Optimal Substructure)

 부분 문제의 최적 결과 값을 이용해 전체 문제의 최적 문제 결과로 이용 가능한 경우

 

② 문제의 변수 파악 및 관계식 정리

일단 나같은 경우는 예제를 한 6~10개를 적어놓고 무슨 관계가 있는지 겁나 고민한다... 솔직히 더 좋은 방법을 모르겠다. 어쨋든 이렇게 해서 점화식을 파악한다. 예를 들어 피보나치 수열은 f(n) = f(n-1) + f(n-2) 이다. 그리고 정해진 값을 설정해야 한다. 예를 들어 피보나치 같은 경우는 f(0) = 0, f(1) = 1으로 0과 1에 대해 지정해줘야 한다.

 

③ 메모이제이션

 점화식을 알아냈다면 점화식에 따른 결과 값을 배열에 저장한다. 점차 저장하면서 목적인 값에 도달하도록 설계한다. 나같은 경우는 dp배열을 만들어서 이 배열에 각 값들을 저장해서 점차 목적값에 도달하도록 한다. 

 

④ 구현

반복문 or 재귀 형식으로 구현