[Algorithm] DP (Dynamic Programming) : 동적 계획법

중복되는 연산을 줄인다

우선 다이나믹 프로그래밍의 다이나믹은 사실 간지를 위해 사용한 이름으로 동적인 의미와는 상관이 없다...

 

다이나믹 프로그래밍은 약간 더 메모리를 사용하면 연산속도를 비약적으로 증가시킬 수 있는 방법으로 두가지 조건을 만족할 때 사용할 수 있다.

 

1. 큰 문제를 작은 문제로 나눌 수 있다.

2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

 

두 조건을 만족하는 가장 대표적인 예시는 피보나치 수열이다.

피보나치 수열

피보나치 수열은 점화식을 가지고 있다.  이전 2개의 항의 값에 영향을 받는다는 점을 이용해 재귀함수로 구현할 수 있다.

점화식

아래는 점화식을 재귀함수로 구현한 코드이다.

#include <cstdio>
using namespace std;
int	fibonacci(int n)
{
	if (n == 0)
    	return (0);
    if (n == 1)
    	return (1);
    return (fibonacci(n - 2) + fibonacci(n -1));
}

int main()
{
	int n;
    scanf("%d", &n);
    printf("%d\n", fibonacci(n));
}

재귀함수는 치명적인 단점이 있다. 바로 n이 커지면 커질 수록 수행시간이 기하급수적으로 늘어간다는 것이다.

예를들면 n = 30 이면 약 10억 가량의 연산을 수행해야 한다. 

동일한 함수가 반복적으로 호출되는 점 때문에 이미 한번 계산 했지만 계속 호출 될 때마다 계산을 하게 되는 것이다.

 

이러한 문제는 중복되는 연산을 줄이는 다이나믹 프로그래밍을 사용하면 효율적으로 해결할 수 있다.

 

1. 탑다운(top-down) 

위에 작성한 코드 처럼 재귀 호출을 사용하는 방법을 탑다운(top-down) 방식이라 한다.

가장 먼저 호출하는 문제는 가장 큰 문제이기 때문에 큰 문제부터 방문하기 때문에 이런 명칭이 붙었고 메모이제이션 기법을 사용해서 중복을 줄일 수 있다. 장점은 가독성이 좋고 본래 점화식을 이해하기 쉽다.

재귀함수로 구현하는 대부분의 방식이 탑다운이다.

 

2. 바텀업(bottom-up) 

반복문을 사용하는 방법을 바텀업(bottom-up) 방식이라고 부르며, 가장 작은 문제들부터 차례차례 답을 쌓아올려가기 때문이다. 장점은 함수를 별개로 부르지 않아 시간과 메모리를 소량 더 절약할 수 있다.

 

3. 메모이제이션(Memoization)

하위 문제를 해결할때 중복된 계산을 막기 위해 결과를 배열에 저장한 뒤 다음 계산이 필요할 때 저장된 값을 불러와 중복을 없앨 수 있다.

이러한 기법을 메모이제이션(memoization)이라고 한다.