도입

동적 계획법은 중복되는 부분 문제들의 답을 미리 저장함으로써 속도의 향상을 꾀하는 알고리즘 설계 기법입니다.

중복되는 부분 문제

동적 계획법은 큰 의미에서 분할 정복과 같은 접근 방식을 의미합니다. 동적 계획법을 사용하는 알고리즘들 또한 처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산하고, 이 답들로부터 원래 문제에 대한 답을 계산해 내기 때문입니다. 동적 계획법과 분할 정복의 차이가 발생하는 부분은 문제를 나누는 방식입니다. 동적 계획법에서 어떤 부분 문제는 두 개 이상의 문제를 푸는데 사용될 수 있기 때문에, 이 문제의 답을 여러 번 계산하는 대신 한 번만 계산하고 계산 결과를 재활용함으로써 속도의 향상을 꾀할 수 있습니다. 그러기 위해서는 각 문제의 답을 메모리에 저장해 둘 필요가 있지요. 이때 이미 계산한 값을 저장해 두는 메모리의 장소를 캐시라고 부르며, 두 번 이상 계산되는 부분 문제를 중복되는 부분 문제라고 부릅니다.

메모이제이션(memoization)

메모이제이션이란 함수의 결과를 저장하는 장소를 마련해 두고, 한 번 계산한 값을 저장해 뒀다 재활용하는 최적화 기법을 말합니다.

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

메모이제이션을 적용하려면 참조적 투명 함수의 경우에만 적용할 수 있습니다. 왜냐하면 입력이 같은데 외부 요소에 따라 다른 값이 반환된다면 캐싱을 할 수 없기 때문입니다. 여기서 참조적 투명 함수란 입력이 고정되어 있을 때 그 결과가 항상 같은 함수를 말합니다.

메모이제이션 구현 패턴

메모이제이션을 구현할 때 한 가지 패턴을 정해두고 항상 같은 형태로 구현하기로 하면 작성하기도, 버그를 찾기도 쉬워집니다.
다음과 같은 재귀 함수가 있다고 합니다.

// a와 b는 각각 [0, 2500) 구간 안의 정수
// 반환 값은 항상 int형 안에 들어가는 음이 아닌 정수
public int someObscureFunction(int a, int b);

이 함수를 메모이제이션으로 구현하는 패턴은 아래와 같습니다.

• 항상 기저 사례를 제일 먼저 처리합니다. 입력이 범위를 벗어난 경우 등을 기저 사례로 처리하면 매우 유용합니다. 기저 사례를 먼저 확인하지 않고 $cache[]$에 접근하면 범위를 벗어나는 등의 오류가 있을 수 있기 때문입니다.
• 함수의 반환 값이 항상 0 이상이기 때문에 $cache[]$를 모두 -1로 초기화합니다. $cache[]$의 해당 위치에 적혀 있는 값이 -1이라면 이 값은 계산된 반환 값일리 없습니다. 만약 함수의 반환 값이 음수일 수도 있다면 이 방법은 사용할 수 없습니다.
• 함수를 반환하기 전에 $cache[]$의 값을 변경해줍니다. C++과 달리 자바는 포인터 연산이 없으므로 따로 저장해줘야 합니다.

아래는 메모이제이션의 사용 예입니다.

// 전부 -1로 초기화해 둡니다.
public static int cache[2500][2500];
// a와 b는 각각 [0, 2500) 구간 안의 정수
// 반환 값은 항상 int형 안에 들어가는 음이 아닌 정수.
public int someObscureFunction(int a, int b) {
	// 기저 사례를 처음에 처리한다
    if (...) return ...;
    // (a, b)에 대한 답을 구한 적이 있으면 곧장 반환
    if (cache[a][b] != -1) return cache[a][b];
    // 여기에서 답을 계산합니다.
    ...
    // 함수를 반환하기 전에 답을 cache에 저장합니다.
    cache[a][b] = result;
    return result;
}
public static void main(String[] args) {
    // Arrays.fill() 함수를 이용해 cache 배열을 초기화합니다.
    for (int i = 0; i < cache.length; i++) {
    	Arrays.fill(cache[i], -1);
    }
}

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

메모이제이션의 시간 복잡도를 분석하는 과정은 처음에는 약간 헷갈릴 수 있습니다. 각 입력에 대해 함수를 처음으로 호출할 때와 다음으로 호출할 때 걸리는 시간이 다르기 때문이죠. 그러나 메모이제이션을 사용하는 알고리즘의 시간 복잡도를 굉장히 간단하게 (주먹구구로) 계산할 수 있는 방법이 있습니다.
(존재하는 부분 문제의 수) * (한 부분 문제를 풀 때 필요한 반복문의 수행 횟수)
물론 이 식은 수행 시간의 상한을 간단히 계산할 수 있는 방법일 뿐이며, 항상 정확하지는 않습니다. 예를 들어 존재할 수 있는 모든 부분 문제 중 일부분만을 계산해도 답을 찾을 수 있는 경우에는 실제 수행 시간이 이 식보다 훨씬 작을 수 있기 때문입니다.

동적 계획법 레시피

대개 동적 계획법 알고리즘의 구현은 다음과 같은 두 단계로 이루어집니다.

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

물론 이 설명은 대단히 단순화 한 것입니다. 문제 유형별로 유의해야 할 점과 알고리즘을 고안하는데 필요한 과정들은 동적 계획법 테크닉에서 소개하겠습니다.

최적 부분 구조

최적 부분 구조란 어떤 문제와 분할 방식에 성립하는 조건입니다. 각 부분 문제의 최적해만 있으면 전체 문제의 최적해를 쉽게 얻어낼 수 있을 경우 이 조건이 성립합니다. 동적 계획법으로 문제 해결을 할 때 단순하게 모든 경우의 수를 저장하려 한다면 메모리를 너무 많이 사용해야할 수 있습니다. 최적 부분 구조가 성립하는지 잘 찾아서 필요한 정보만 저장한다면 효율적으로 해결할 수 있습니다.

참고문헌: 구종만, 프로그래밍 대회에서 배우는 알고리즘 문제해결전략, 인사이트, (2012)