Live of Thinking

재귀를 설명한 글의 끝부분에서 입력값이 조금만 커져도 재귀호출 횟수가 급격하게 늘어나는 문제점에 대해서 언급했는데, 이렇게 되는 이유는 중복되는 부분 문제를 계산하는 횟수가 너무 많기 때문이다. 이 문제를 풀어 보면 알 수 있지만 피보나치 수를 구하기 위해서 이 글에 나온 것처럼 코드를 짜면 함수 호출의 횟수 자체가 피보나치 수만큼 증가하기 때문에 이렇게 해서는 빠른 코드를 짤 수 없다.

하지만 중복되는 부분 문제를 살펴보면 중복되는 부분 문제에 대한 답이 항상 같기 때문에, 만약 어떤 부분 문제의 답을 계산했다면 그 계산 결과를 저장한 뒤 나중에 같은 부분 문제를 풀 때 기존에 계산한 답을 사용하면 되므로 성능을 크게 향상시킬 수 있다. 이러한 방법을 메모이제이션(Memoization)이라고 한다. (Memorization이 아니다. 두 단어는 각각 Memo와 Memorize에서 파생된 말로 기본형부터 다르다.) 또한 메모이제이션을 활용해서 문제를 해결하는 방법을 동적 계획법(Dynamic Programming, DP)이라고 한다. (줄임말인 DP 역시 매우 많이 쓰이는 단어이므로 알아 두는 것이 좋다.) 동적 계획법 역시 그리디와 마찬가지로 매우 자주 등장하고, 활용되는 범위도 넓기 때문에 많은 연습이 필요하다.

이 글에 나온 코드를 메모이제이션을 사용하여 훨씬 빠른 코드로 바꾸면 이렇게 된다.

int f(int n)
{
    if(a[n])return a[n];
    if(n < 2)return a[n] = 1;
    return a[n] = f(n-2) + f(n-1);
}

배열을 전역 변수로 선언한다면 모든 원소가 $0$으로 초기화되고, 피보나치 수열에는 $0$이 등장하지 않으므로 $a[n]$이 $0$이 아니라는 것은 이전에 $f(n)$이 계산되었다는 것과 같다. 따라서 이 값을 바로 쓸 수 있다. 만약 그렇지 않다면 이전에 계산한 정보들을 바탕으로 $f(n)$을 계산에서 $a[n]$에 저장한다. 이때 값을 저장하는 배열 $a$를 DP 테이블(DP Table)이라고 한다.

위의 코드는 가장 큰 부분 문제부터 접근하여 재귀호출을 통해서 답을 구하는데, 이러한 방식을 탑다운(Top-Down)이라고 한다. 이와 대비되는 개념으로 바텀업(Bottom-Up) 방식이 있는데, 이 방식은 기저 사례에서 시작해서 점점 큰 부분 문제를 해결하고 최종적으로 원래 문제의 답을 구한다. 바텀업 방식은 대부분 재귀함수 없이 구현할 수 있어서 실행시간이나 메모리 사용량의 측면에서 탑다운 방식보다 약간 더 효율적이다. 다만 성능에 크게 영향을 주지 않는 경우도 많고 탑다운 방식의 코드는 더 직관적이어서 가독성의 측면에서 더 효율적인 경우가 많으므로 상황에 따라 적절한 방식을 선택하면 된다. 피보나치 수를 구하는 코드를 바텀업 방식으로 짜면 이렇게 된다.

a[0] = a[1] = 1;
for(int i = 2;i <= n; i++)a[i] = a[i-2] + a[i-1];

두 코드 모두 $\Theta(n)$의 시간복잡도를 가짐을 확인할 수 있다.

동적 계획법은 유형이 다양하므로 카테고리 E에서 더 자세히 살펴볼 것이기 때문에 일부 유형에 해당하는 연습문제는 넣지 않았다.

[연습문제]

BOJ 1463. 1로 만들기 (Silver III)

$f(0)=0$이고 $f(n)=\min(f(n/3),f(n/2),f(n-1))+1$인데 $f(n/3)$과 $f(n/2)$는 각각 $n$이 $3$의 배수일 때와 $2$의 배수일 때만 포함된다. 만약 그렇지 않다면 해당 값들을 빼고 계산해야 한다.

BOJ 1932. 정수 삼각형 (Silver I)

$i$행 $j$열의 값을 $a_{i,j}$라고 하고 $i$행 $j$열의 수를 선택했을 때 얻을 수 있는 최대합을 $s_{i,j}$라고 하면 $s_{i,j}=\max(s_{i-1,j-1},s_{i-1,j})+a_{i,j}$와 같다. 즉 $i$행 $j$열의 값을 선택하기 위해서는 $(i-1)$행 $(j-1)$열 또는 $(i-1)$행 $j$열의 값을 선택해야 하기 때문에 두 경우의 최대합 중 더 큰 값에 $i$행 $j$열의 값을 더하면 $i$행 $j$열의 값을 선택했을 때의 최대합이 나오는 것이다. 물론 위의 두 값 중 한 값이 존재하지 않을 수도 있는데 이때는 합을 $0$으로 간주하면 된다.

BOJ 12865. 평범한 배낭 (Gold V)

배낭 문제 또는 냅색 문제(Knapsack Problem)이라고 불리는 유명한 문제이다. 각각의 물건을 배낭에 넣을지 안 넣을지를 결정해야 하는데, 이것을 $i$번째 물건까지 고려했을 때 배낭에 넣은 물건의 가치가 $j$일 때의 최소 무게, 또는 $i$번째 물건까지 고려했을 때 배낭에 넣은 물건의 무게가 $j$일 때의 최대 가치를 DP 테이블에 채우면 된다. 후자의 경우 반복 횟수가 $1000$만까지 올라갈 수 있지만 제한시간 내에 충분히 통과한다.

BOJ 13302. 리조트 (Gold V)

$i$일째에 $j$장의 쿠폰이 있을 때 지불한 비용의 최솟값을 DP 테이블에 채워 넣으면 된다.

BOJ 17623. 괄호 (Gold II)

괄호값이 $k$인 문자열 $s_k$ 중에서 $\text{val}(s)$의 값이 가장 작은 문자열을 $t_k$라고 하면 $t_k$는 다음 문자열 중에서 $\text{val}$값이 가장 작은 문자열이 된다. 기저 사례는 $k = 1, 2, 3$일 때이다.