[알고리즘] 동적 계획법(Dynamic Programming): 메모이제이션(memoization)

0. 메모이제이션(memoization)

메모이제이션(memoization)
이전에 계산한 값을 저장해서 매번 다시 계산하지 않도록 하여 전체적인 실행속도를 빠르게 하는 기술이다.
동적 계획법의 핵심이 된다.

 

순수함수만 메모이제이션이 가능하다.

순수함수란?
1. 함수의 실행이 부수효과를 일으키지 않는 함수
2. 동일한 input에 대해 동일한 output을 반환하는 함수
3. 매개변수 이외에 함수 외부의 것들을 사용하지 않는 함수

 

메모이제이션은 추가적인 메모리 공간이 필요하다.

추가로 재귀 함수 호출로 인한 시스템 호출 스택을 사용하게 됨에 따라 실행 속도 저하 또는 오버 플로우가 발생할 수 있다.

0-1. 예시

가장 일반적인 피보나치 수열 알고리즘 코드이다.

fibo(n) {
    if (n <= 2)
        return 1;
    
    return fibo(n - 1) + fibo(n - 2);
}

 

피보나치 수열 알고리즘에 메모이제이션을 적용한 코드이다.

memo[]: 메모를 위한 배열
        memo[0]은 0으로, memo[1]은 1로 나머지는 모두 -1로 초기화한다.
        
fiboWithMemo(n) {
    if memo[n] == -1
        memo[n] = fiboWithMemo(n - 1) + fiboWithMemo(n - 2);
        
    return memo[n];
}

---

1. 동적 계획법(Dynamic Programming)

작은 부분 문제들의 해들을 구하고 이들을 이용하여 보다 큰 크기의 부분 문제들을 해결하여, 최종적으로 원래 주어진 문제를 해결하는 알고리즘 설계 기법이다.

 

동적 계획법을 적용하기 위해선 아래 2가지 요건을 가지고 있어야 한다.

1. 중복 부분문제 구조(Overlapping subproblems)
2. 최적 부분문제 구조(Optimal substructure)

1-1. 중복 부분문제 구조(Overlapping subproblems)

• DP는 큰 문제를 이루는 작은 문제들을 먼저 해결하고 작은 문제들의 최적 해(Optimal Solution)를 이용하여 순환적으로 큰 문제를 해결한다.
  • 순환적인 관계(recurrence relation)를 명시적으로 표현하기 위해서 동적 계획법에서는 일반적으로 수학적 도구인 점화식을 사용한다.
• DP는 문제의 순환적인 성질때문에 이전에 계산했던 작은 문제의 해가 다른 어딘가에서 필요하게 되는데(Overlapping subproblems) 이를 위해 DP에서는 이미 해결된 작은 문제들의 해를 따로 저장하게 된다.
• 이렇게 저장된 해들이 다시 필요할 때마다 해를 얻기 위해 다시 문제를 재계산하지 않고 참조를 통해서 중복된 계산을 피하게 된다.

1-2. 최적 부분문제 구조(Optimal substructure)

• 동적 계획법이 최적화에 대한 어느 문제에나 적용될 수 있지 않다. 주어진 문제가 최적화의 원칙(Principle of Optimality)을 만족해야만 동적 계획법을 효율적으로 적용할 수 있다.
• 최적화의 원칙이랑 어떤 문제에 대한 해가 최적일 때 그 해를 구성하는 작은 문제들의 해 역시 최적이어야 한다는 것이다. 동적 계획법의 방법 자체가 큰 문제의 최적 해를 작은 문제의 최적해를 이용해 구하기 때문에 만약 큰 문제의 최적해가 작은 문제들의 최적 해로 구성되지 않는다면 이 문제는 동적 계획법을 적용할 수 없다.

최적화의 원칙이 적용되지 않는 예시: 최장 경로(Longest Path) 문제

• A에서 D로의 최장 경로는 [A, C, B, D]가 된다.
• A에서 C로의 최장 경로는 [A, C]가 아니라 [A, B, C]이다.
• 따라서 A에서 D로 가는 문제의 작은 문제인 A에서 C로의 경로가 최적 해가 아니기에 최장경로문제는 DP로 해결할 수 있다.

---

2. DP 적용 접근 방법

1. 문제의 유형을 파악
   • 최적해를 구하는 문제인지, 경우의 수를 구하는 문제인지 파악하라
2. 부분문제를 식벽
3. 동적테이블을 정의(상태 표현)
   • memo[i]가 무엇을 의미하는지 정의해라. i는 무슨 상태인지, 값은 무엇을 의미하는지
4. 부분문제들의 관계를 파악해서 점화식을 도출
   
   • memo[i]와 memo[i - 1], memo[i - 2]의 관계 등을 파악해라
   • 관계 수립이 되지 않는 base case도 파악해라(ex: 피보나치 수열의 1번째 항)
5. 동적테이블 초기화 및 부분문제의 해를 점화식을 통해 계산
6. 큰 문제의 해 도출

---

3. 해당 문제를 DP라고 판단하는 방법

1. 먼저 하향식접근(재귀)을 시도해본다.
2. 상태공간트리를 작성하는 과정에서 중복 호출이 많은지 판단한다.
3. 중복 호출이 많다면 상향식접근으로 시도해본다.

---

4. DP 구현

fiboWithDP(int n) {
    long[] D = new long[n + 1];
    D[1] = D[2] = 1;

    for (int i = 3; i <= n; i++) {
        callCnt3++;
        D[i] = D[i - 1] + D[i - 2];
    }

    return D[n];
}