동적 계획법

동적 계획법 (Dynamic Programming)은 최적화 문제를 연구하는 수학이론에서 왔으며, 큰 의미에서 분할 정복과 같은 접근 방식을 의미한다.

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

DP에서 어떤 부분 문제는 2개 이상의 문제를 푸는데 사용할 수 있기 때문에 이 문제의 답을 여러 번 계산하는 대신에 한번만 계산하고 계산결과를 재활용 함으로서 속도의 향상을 꾀할 수 있다.

Dynamic Programming의 고안자 벨만은 Dynamic이라는 단어가 멋있어서 선택했다고 한다..

메모이제이션

동적 계획법으로 가장 유명한 문제는 이항계수이다.

위 점화식을 이요하면 $n$, $r$값이 주어지면 $\binom{n}{r}$의 값을 반환하는 함수를 아래와 같이 작성 할 수 있다.

def bino(n, r):
	if r == 0 or n == r:
    	return 1
    return bino(n-1, r-1) + bino(n-1, r)

이 과정을 따라가 bino(4, 2)를 계산한다면 아래의 과정을 따른다.

bino(4,2) ➡ bino(3,1) ➡ bino(2,0) ➡
bino(2,1) ➡ bino(1,0) ➡ bino(1,1) ➡
bino(3,2) ➡ bino(2,1) ➡ bino(1,0)

이때 bino(2,1)이 2번 계산된다는 것을 알 수 있다. 만약 $n$과 $r$이 매우 커진다면 조합 폭발(Combinational Explosion)이 일어난다. 예를 들어 bino(25, 12)를 계산하려면 1천만번의 함수 호출이 필요하다.

입력인 $n$, $r$이 정해져있을 때, bino(n, r)의 반환값이 일정하다는 사실을 이용하면 이 문제에서 중복을 제거할 수 있다. 각 $n$, $r$ 조합에 대해 답을 저장하는 캐시 배열을 만들어서 각 입력에 대한 반환 값을 저장해뒀다 재 활용하면 된다. 이 최적화 기법을 메모이제이션 이라고 한다.

아래는 메모이제이션을 적용한 최적화 된 코드이다.

cache = [[0 for _ in range (10)] for __ in range(10)]
def bino(n, r):
    if r == 0 or n == r:
        return 1
    
    if cache[n][r]:
        return cache[n][r]
    
    cache[n][r] = bino(n-1, r-1) + bino(n-1, r)
    return cache[n][r]

time.time()을 이용하여 두 함수의 수행시간을 비교했을때 bino(24,12)의 수행시간은 아래와 같이 차이가 났다

#1
0.5814464092254639

#2
0.0

메모이제이션을 적용할 수 있는 경우

수학의 함수와 다르게 프로그래밍의 함수는 전역변수나 입력파일, 클래스의 맴버변수 등 수많은 입력에 의해 작동하기 때문에 같은 입력을 넣더라도 다른 값을 반환할 수 있습니다. 함수의 반환 값이 그 입력값 만으로 결정되는지의 여부를 참조적 투명성 (referential transparency)라고 부른다.
입력 값이 고정되어있을때 그 결과가 항상 같은 함수들을 참조적 투명 함수 (referential transparency function)이라고 부른다.

당연하게도 메모이제이션은 참조적 투명 함수에서만 적용이 가능하다. 입력이 같은데 외부 요소에 따라 다른 값이 반환된다면 캐싱을 할 수 없다.

메모이제이션 구현 패턴

1. 항상 기저 사례를 가장 먼저 처리한다. 입력이 범위를 벗어난 경우 등을 기저 사례로 처리하면 유용한데, 기저 사례를 먼저 확인하지 않고 캐시에 접근하면 Index Error가 발생할 수 있다.

2. 해당 답을 구한 적 있으면 그대로 반환

3. 기저사례 또는 답에 해당하지 않는다면 값을 계산

메모이제이션 시간복잡도 분석

메모이제이션을 사용하는 알고리즘의 시간 복잡도를 굉장히 간단하게 계산할 수 있는 방법은 아래의 수식을 따른다

bino 함수에 적용

bino(n, r)에서 $r \le n$ 이므로 $r$의 최대치는 $n$이고, 이를 계산할 때 만날 수 있는 부분 문제의 수는 최대 $n^2$이다.

각 부분문제를 계산할 때 걸리는 시간은 $O(1)$ (반복문이 없으므로)이다.

위의 식에 따라 bino 함수를 계산하는데 걸리는 시간복잡도는 $O(n^2) \times O(1)$
즉 $O(n^2)$이다.

메모이제이션 구현 레시피

1. 주어진 문제를 완전탐색을 이용해 해결한다
2. 중복된 부분문제를 한분만 계산하도록 메모이제이션을 적용한다.

용어

• 캐시 (Cache) : 이미 계산한 값을 저장해두는 메모리의 장소

• 중복되는 부분 문제 (Overlapping Subproblems) : 두 번 이상 계산되는 부분 문제

• 조합 폭발 (Combinational Explosion) : 분할의 깊이가 깊어지면 깊어질 수록, 계산의 중복횟수는 지수적으로 증가하는 현상.

• 메모이제이션 (Memoization) : 함수의 결과를 저장하는 장소를 마련해두고, 한 번 계산한 값을 저장해 뒀다가 재활용하는 최적화 기법