[알고리즘] 동적 계획법(Dynamic Programming)

동적 계획법 ( Dynamic Programming )

---

동적 계획법 개요

동적 계획법은 큰 의미에서 분할 정복과 같은 접근 방식을 의미한다. 동적 계획법을 사용하는 알고리즘들 또한 처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산하고, 이 답들로부터 원래 문제에 대한 답을 계산해 내는 방식이기 때문이다.

동적 계획법과 분할 정복의 가장 큰 차이는 문제를 나누는 방식이다. 동적 계획법에서 어떤 부분 문제는 두 개 이상의 문제를 푸는데 사용 될 수 있기 때문에 이를 여러번 계산하는 것 대신 한번만 계산하게 만듦으로써 속도 향상을 꾀할 수 있다. 그러기 위해선 부분 문제를 메모리에 저장해 둘 필요가 있는데 이 메모리 장소를 캐시(cache)라고 부른다.

이를 피보나치 수열 함수를 예로 설명해보겠다.

위의 그림은 피보나치 함수를 분할 정복방식으로 구현한 것이다. 함수 이름을 fib(n) 이라고 했을때, 예시처럼 fib(5)를 구하기 위해선 총 15번의 함수 호출이 필요하다. 이때, fib(2)는 총 3번 호출되는것을 볼 수 있는데 이는 동일한 계산과정을 3번이나 반복하게 되어 알고리즘의 실행시간이 길어지게 된다.

이런 중복계산을 캐시에 저장시킨 뒤 필요할 때마다 결과값만을 가져와서 사용하는 방식을 동적 계획법 ( Dynamic Programming ) 이라고한다.

동적 계획법 알고리즘의 가장 유명한 예 중 하나를 더 설명해보겠다. 바로 이항 계수의 계산이다. 이항 계수는 서로다른 n개의 원소중에서 r개의 원소를 순서없이 골라내는 방법의 수를 계산하는 것으로 다음과 같은 점화식이 성립한다.

이 점화식을 활용하여 n,r의 값이 주어질 때 그 결과를 반환하는 함수 bino(n,r)를 다음과 같이 작성할 수 있다.

int bino(int n, int r) {
	if(r == 0 || n == r) return 1;
	return bino(n-1,r-1) + bino(n-1,r)

이 코드는 분할 정복 알고리즘을 사용한 것으로 중복 계산이 발생한다.

이를 동적 계획법 알고리즘으로 변환하여 작성한 코드는 다음과 같다.

// -1로 초기화해둔다
int cache[30][30];

int bino2(int n, int r) {
	if(r == 0 || n == r ) return 1;
	
	if(cache[n][r]!= -1) 
	return cache[n][r];

	return cache[n][r] = bino2(n-1,r-1) + bino2(n-1,r);

코드처럼 cache라는 배열을 생성해준뒤 이곳에 값을 저장하는 방식을 사용하면 된다. 이를 메모이제이션(memoization) 이라고 부른다.

메모이제이션 구현 패턴

동적계획법은 가장 흔한 문제 유형 중 하나이기 때문에 메모이제이션을 굉장히 많이 구현하게 된다. 그렇기 때문에 한가지 패턴을 정해놓고 문제를 항상 같은 형태로 풀어가게 되면 문제 풀이에 도움이 많이 된다. 이 패턴을 소개해 보겠다.

1. 항상 예외처리를 제일 먼저 처리해라.

   예외상황은 각종 오류를 유발하므로 제일 먼저 처리해놓는 것이 좋다.

2. cache를 초기화 해줘라. feat. memset( )

   초기화 할때는 C++ STL에 내재되어 있는 memset( ) 메소드를 활용하면 편리하다. memset ( 메모리시작주소, 값, 크기 ) 를 사용하면 된다. EX ) memset ( cache, -1, sizeof(cache) )

3. return 값을 활용해라. cache를 사용할 때마다 매번 cache[n][r]처럼 쓰지말고 return값을 활용해라.

4. 점화식을 만들어라.

===========================================================

※ 2022-01-14 추가

근 한달간 DP문제를 쭉 풀어보면서 깨달은 문제풀이 방법을 정리해보도록 하겠다.

1. 문제에서 구하려고 하는 답을 점화식으로 나타낸다.

DP모든 문제는 점화식으로 표현이 가능하다. 점화식으로만 표현한다면 문제는 사실상 거의 다 풀린것이나 다름없다. 점화식에는 꼭 한가지 식만 들어갈 필요도 없다. 여러 식을 혼합해도 되고 변수를 이용해도 좋다 백준 14002번 : 가장 긴 증가하는 부분 수열4 문제에서 여러 식과 변수가 혼합된 점화식을 살펴볼 수 있다!

2. 점화식은 이차원 배열을 사용하기도 한다.

이차원 배열을 잘 활용해 점화식을 만들면 편리한 경우도 많다. 백준 15990번 : 1,2,3 더하기 5 문제는 이차원 배열을 사용하는 대표예제이다.

3. 최소값, 최대값을 구할때는 초기화가 중요하다.

최소, 최대값은 비교대상이 필요하기 때문에 메모이제이션을 할 때 초기화를 해주는 것이 좋다. 어떤 값으로 초기화 해주는지는 문제에 따라 잘 고려하여 해줘야만 한다. 보통 최소값을 구하기 위한 초기값은 변수의 범위 이상 값을 넣어주고
최대값을 구하기 위한 초기값은 0을 넣어주는것이 일반적이지만 절대적이지는 않다!

4. Top-Down / Bottom-Up 두가지 방식 모두 생각하라!

보통 두가지 방식으로 같이 풀리는 경우가 많지만 그렇지 않은 경우도 꽤 있다. 두가지 방식을 동시에 생각하는 사고를 반드시 가지자!!