[Algorithm] 동적 계획법(Dynamic Programming) - 메모제이션

동적 계획법이란

수학과 컴퓨터 공학, 그리고 경제학에서 동적 계획법(動的計劃法, dynamic programming)이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다.

- 위키피디아 (https://ko.wikipedia.org/wiki/%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95) -

그럼 동적 계획법은 어떤 경우에 사용하게될까요?

 

Dynamic Programming은 작은 문제들로 나눈 뒤 합쳐서 결과를 얻는다는 점에서 분할 정복과 비슷한 방식이지만 분할 정복에서는 중복될 수 있는 부분을 Dynamic Programming에서는 중복되는 부분을 저장(캐시)해서 한번만 계산하도록 한다는 점에서 차이점이 있습니다.

 

Dynamic Programming이 필요한 경우를 비교하기 위해 재귀함수와 비교할 수 있습니다.

 

이항 계수를 구하는 경우를 생각해봅시다.

이항 계수(n r)는 n개의 서로 다른 원소 중에서 r개의 원소를 순서없이 골라내는 방법의 수를 나타내는 것으로, 점화식으로 표현하면 다음과 같습니다.

(n r) = (n-1 r-1) + (n-1 r)

 

이 점화식을 사용해서 재귀 함수로 표현하면 다음과 같다.

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

 

위와 같이 작성하면 상당히 깔끔한 코드로 이항계수 (n r)을 구할 수 있습니다.

하지만 위에 식을 실제로 실행시킨다면 함수 bino()는 얼마나 호출될까요?

 

재귀함수 호출

재귀 함수를 사용했을 때 bino(4,2)는 총 11번의 함수를 호출하게 됩니다. 사실 현대의 컴퓨터에게 이정도 계산은 순식간에 이루어지지만 문제는 이 재귀함수는 값이 커짐에 따라 호출횟수가 기하급수적으로 증가한다는 것입니다.

 

우리가 주의 깊게 볼 부분은 bino(2, 1)부분이 2번 호출되고 그 밑에 있는 함수들도 같이 2번씩 호출된다는 것입니다. 이렇게 중복 호출되는 부분들을 한번씩만 호출한다면 훨씬 효율적으로 계산할수 있습니다.

 

그렇다면 어떻게 해야 중복되는 부분을 줄일 수 있을까요?

한번 계산한 결과값을 어딘가에 저장해두고 필요할 때마다 꺼내쓴다면 중복으로 계산을 할 필요가 없을것입니다.

 

int dp[10][10];

int bino(int n, int r){
    if(r == 0 || n == r){
    	return 1;
    }
    //저장된 적이 있다면
    if(dp[n][r] != 0){
    	return dp[n][r];
    }
    //저장된 적이 없다면
    return dp[n][r] = bino(n-1, r-1) + bino(n-1, r);
}

이렇게 저장(캐시)하는 Dynamic Programming 기법을 메모제이션(memoization)이라고 합니다.

 

메모제이션을 사용할 때 주의해야할 점은 입력이 벗어나거나 default가 되는 값을 잘 설정해야한다는 것입니다.

위 코드에서 if( r == 0 || n == r ) 가 없다면 n-1 이나 r-1의 값이 음수가 되면서 범위에 벗어나게 될 것입니다.