다이나믹 프로그래밍(동적 계획법) 개요

1. 소개

 

프로그래밍 문제에 가장 자주 출현하는 디자인 패러다임이다.

메모리를 희생하여 속도를 얻는 가장 대표적인 방식이기도 하다.

이름이 굉장히 거창하지만 사실 의미는 없고 단순히 멋있어서 지은 것이라고...

종만북(프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략)에서는 DP의 특성 상 동적 프로그래밍보다는 동적 계획법이 더 알맞은 번역이라고 소개하고 있다.

2. 풀이법

 

분할 정복과 접근방식이 유사하다.

주어진 문제를 더 작은 문제들로 나누고 각 조각들의 답을 도출해내기 때문이다.

단, DP에서는 단 한 번만 계산하고 그 결과를 다시 재활용하여 속도를 향상시킨다는 점에서 다르다.

가장 쉽게 생각해볼 수 있는 사례로 이항계수가 있다.

BOJ 이항 계수 2 링크

위키백과(파스칼의 삼각형)

위키백과의 공식대로 이항계수를 분할 정복처럼 작성한다면 아래의 재귀함수로 짤 수 있을 것이다.

int func(int n, int k)
{
	if (k == 1 || n == k) 
		return 1;

	return func(n - 1, k - 1) + func(n - 1, k);
}

이 코드엔 속도에서 문제가 발생한다.

func(5, 3) = func(4, 2) + func(4, 3)

func(4, 2) = func(3, 1) + func(3, 2)

func(4, 3) = func(3, 2) + func(3, 3)

...

...

함수 하나하나는 재귀적으로 다른 함수를 다시 호출한다.

그리고 중복되어 호출되는 부분이 존재한다.

n, k가 클 수록 중복 횟수 역시 기하급수적으로 증가할 것이다.

배열에 계산 결과를 저장하면 이 문제를 쉽게 해결할 수 있다.

이 방법을 메모이제이션이라고 한다.

대부분의 DP 문제에서는 기저사례를 처리해주어야 한다.

메모이제이션으로 보통 배열을 많이 사용하는데 인덱스가 범위를 벗어날 수 있기 때문이다.

위의 이항 계수 문제같은 경우 n == k, n == 1인 경우에 무조건 1로 설정한다.

이 정도만 알면 준비는 끝이다.

많은 문제를 풀어보면서 응용력을 키우면 되겠다.