동적 계획법

[1. 도입]

• 큰 의미에서 분할 정복과 같은 접근 방식을 의미한다
• 다만, 어떤 부분 문제가 두 개 이상의 문제를 푸는데 사용 될 때 이 문제의 답을 한번만 계산 하고 향후 이 결과를 재활용하여 속도 향상을 노려볼 수 있다.
• 여기서 두 번 이상 계산 되는 부분 문제를 중복되는 부분 문제라 한다.

 

[2. 메모이제이션]

• 한 번 계산한 값을 저장해두었다가 재활용하는 최적화 기법
• 참조적 투명 함수인 경우 적용 가능함
• 참조적 투명 함수란?
  => 입력이 고정되어 있을 때 그 결과가 항상 같은 함수
  => 함수의 반환 값이 그 입력 값만으로 결정되는지의 여부를 참조적 투명성이라 함.

 

[3. 메모이제이션 구현 패턴]

1. 기저 사례를 먼저 처리
   => 입력이 범위를 벗어난 경우, ...
2. 가능한 경우 cache[] 를 모두 -1로 초기화
   => 아직 계산 되지 않음을 의미하는 값이면 됨
   => memset 의 경우 byte 단위로 초기화 하므로, 0 또는 -1 만 유효 함
3. cache[] 의 값을 참조형으로 저장
   => int &ret = cache[n]
   => cache 가 다차원 배열일 때 특히 유용함.
4. 완전 탐색에서 시작해서 부분 문제를 캐쉬로 처리 할 수 있도록.

 

[4. 예제, JUMPGAME]

int board[100][100];
int cache[100][100];
int N;

int jump(int y, int x)
{
    // Basecase 1
    // 입력 좌표가 board 를 벗어난 경우
    if (y >= N || x >= N) {
        // false
        return 0;
    }

    // Basecase 2
    // 입력 좌표가 목표한 위치에 도달 한 경우
    if (y == N-1 && x == N-1) {
        // true
        return 1;
    }

    // memoization
    int &ret = cache[y][x];
    // cache check
    if (ret != -1) {
        return ret;
    }

    const int jumpsize = board[y][x];
    // 현재 시작위치에서 결과위치에 도달 하는 것은
    // 이전 결과에 전혀 영향을 받지 않는 다고 볼 수 있다.
    // => 참조적 투명 함수 조건을 만족함.
    // recursion => cache update
    ret = (jump(y+jumpsize, x) || jump(y, x+jumpsize));
    return ret;
}

 

[5. 예제, TRIANGLEPATH]

#include <algorithm>

int n, triangle[100][100];
int cache[100][100];

int path2(const int y, const int x)
{
    // base case
    // 마지막 row 에 도달한 경우
    if (y == n-1) {
        return triangle[y][x];
    }

    int &ret = cache[y][x];
    if (ret != -1) {
        return ret;
    }

    // 이전 결과가 현재 문제를 해결하는데 영향을 주지 않는다.
    // 최적 부분 구조를 만족함
    // 현재 위치에서 앞으로 계산 될 최대 값은
    // 현재 위치 값 + max(바로 밑으로 이동 할 때의 최대 값, 대각선 밑으로 이동 할 때의 최대값)
    ret = triangle[y][x] + std::max(path2(y+1, x), path2(y+1, x+1));
    return ret;
}

 

[6. 예제, LIS]

#include <vector>
#include <algorithm>

// Bruteforce //
int lis(const std::vector<int>& A)
{
    // Basecase
    if (A.empty()) {
        return 0;
    }

    int ret = 0;
    for (int i = 0; i < A.size(); i++)
    {
        std::vector<int> B;
        for (int j = i+1; j < A.size(); j++)
        {
            // i 번째 보다 큰 원소만 B 에 푸쉬하여
            // 증가 부분 수열을 형성 함.
            if (A[i] < A[j]) {
                B.push_back(A[j]);
            }
        }
        // 더하기 1 은 현재 i 번째의 원소를 포함한 것을 의미함
        ret = std::max(ret, 1 + lis(B));
    }

    return ret;
}

// Memoization

int n;
int cache[101]; // zero-based index 가 아님
int S[100]; // 입력으로 주어진 수열

int lis3(const int start)
{
    int& ret = cache[start+1];
    if (ret != -1) {
        return ret;
    }

    // 현재 선택 한 원소가 수열에 반드시 포함되므로
    // 모든 증가 부분 수열은 최소 1의 길이를 갖는다.
    ret = 1;
    for (int next = start + 1; next < n; next++)
    {
        // start == -1 => 최초 호출인 경우
        if (start == -1 || S[start] < S[next]) {
            // 현재 부분 문제는 이전의 결과의 영향을 받지 않는
            // 최적 부분 구조이다.
            ret = std::max(ret, 1 + lis3(next));
        }
    }

    return ret;
}