[Algorithm/DP] 동적 계획법(Dynamic Programming)

동적 계획법(Dynamic Programming)이란?

• 분할 정복 패러다임 개념을 확장한 것
• 앞서 다룬 분할정복 / 그리디 알고리즘으로 해결할 수 없는 문제 중에서 재귀적으로 표현할 수 있는 문제는 동적 계획법을 이용한 문제 해결 방법이 적합할 수 있다.
• ex)
  • 조합(특정 기준을 만족하는 시퀀스의 조합 또는 순열의 개수 구하기)
  • 문자열과 시퀀스(편집 거리, 최장 공통 부분 시퀀스, 최장 증가 부분 시퀀스 등)
    • 그래프(최단 경로 문제)
    • 머신 러닝(음성/얼굴 인식)

Ex) 피보나치 수열 문제의 특성

• 피보나치 수열은 F(n) = F(n - 1) + F(n - 2)의 재귀적인 관계를 가지고 있다.
  • 위 수식은 이 수열의 재귀 관계를 표현한다.
• 이 수열의 처음 두 원소 F(0), F(1)은 기조 조건(base case)이라고 부르며, 더 이상 재귀가 없어도 해를 구할 수 있는 지점을 나타낸다.
• 피보나치 수열의 n번째 원소를 구하는 문제 접근 방법 중 하나로는 하향식 해법(top-down solution)이 존재한다
  • F5는 F4 + F3과 같고, F4는 F3 + F2와 같고, F3은 F2 + F1과 같고....
  • 전체 해결 방법을 트리 형태로 구성한 재귀 트리의 맨 꼭대기에서 시작해서 기저 조건에 닿을 때 까지 아래쪽 가지로 이동하기 때문
• 트리를 자세히 관찰하면 최종 해답을 찾기 위해 여러 개의 부분 문제 또는 중단 단계 문제를 풀어야 한다는 점을 알 수 있다.
  • 이러한 부분 문제들은 한 번 이상 나타난다는 점 또한 발견할 수 있다.
• 피보나치 수열은 중복되는 부분 문제(overlapping subproblem)라는 특성을 가지고 있다고 할 수 있다.
  • 이는 일반적인 분할 정복 문제와 동적 계획법 문제를 구분하는 특성 중 하나이다.
  • 분할 정복 문제에서는 전체 문제가 독립적인 부분 문제로 나뉘는 경향이 있지만, 동적 계획법의 경우에는 같은 부분 문제가 반복적으로 나타난다.
• 또한 여러 부분 문제가 서로 완전히 동일하다는 것을 알 수 있다.
  • F(4)를 구하기 위해서나, F(3)을 구하기 위해서 부분 문제 F(2)를 구해야 하는데, 두 경우에 F(2)를 구하는 문제는 동일하다.
  • 이를 최적 부분 구조(optimal substructure)라고 부른다.
    • 최적 부분 구조가 동적 계획법 문제를 정의하는 두 번째 특성이다.
    • 전체 문제에 대한 최적해가 부분 문제의 최적해의 조합으로 표현할 수 있을 때 최적 부분 구조를 갖는다고 표현한다.
• 어떤 문제를 동적 계획법으로 해결하려면 중복되는 부분 문제, 최적 부분 구조 두 가지 속성을 만족해야 한다.
  • 중복되는 부분 문제 특성으로 인해 몬제의 복잡도가 입력이 증가함에 따라 기하급수적으로 증가하는 경향이 있지만, 최적 부분 구조를 활용하면 복잡도를 크게 줄일 수 있다.
• 동적 계획법에서는 반복 계산을 피하기 위해 이전에 해결한 부분 문제의 해답을 캐시에 저장하는 방식을 사용한다.

메모이제이션 기법: 하향식 접근 방법

• 메모를 한다는 의미에서 메모이제이션(memoization)이라고 한다.
• 피보나치 수열에 대해 하향식 해법을 재구성할 수 있다.
• 각 단계에서 부분 문제의 해답을 찾으면 이를 배열 구조의 캐시에 저장한다.
  • 배열의 인덱스는 현재의 n값을 사용하며, 여기서 n은 피보나치 수열 문제 풀이 단계의 매개변수 집합 또는 상태(state)를 나타낸다.
• 함수 F(n)이 호출될 때 마다 먼저 F(n)의 상태가 이미 캐시에 저장되어 있는지를 확인하여 캐시에 값이 저장되어 있다면 단순히 이 값을 반환한다.

#include <bits/stdc++.h>
using namespace std;

const int UNKNOWN = -1;
const int MAX_SIZE = 100;

vector<int> memo(MAX_SIZE, UNKNOWN);

int Fibonacci(int n) {
    if (n < 2) return n;

    if (memo[n] != UNKNOWN) return memo[n];

    int result = Fibonacci(n - 1) + Fibonacci(n - 2);
    memo[n] = result;
    return result;
}

• 이러한 방식을 통해 많은 중복 작업을 제거할 수 있다.
• 이처럼 하향식 방식에서 부분 문제의 해를 캐시에 넣어서 사용하는 기술을 메모이제이션이라고 한다.
  • 이는 모든 DP 문제에 적용할 수 있다.
• 다음 조건을 만족함을 가정한다.

1. 고유한 특성은 유지하면서 서로 다른 상태의 유사성을 활용하는 캐시 사용 방식을 고안할 수 있다.
2. 사용 가능한 스택 공간을 초과하기 전에 필요한 모든 부분 문제의 해답을 누적할 수 있다.

• 첫 번째 항목은 부분 문제 해법을 캐시에 인덱싱하여 저장하는 방법이 유효하고 유용해야 한다는 점을 의미한다.
  • 캐시 사용 방법이 유효하려면 같은 의미의 부분 문제 해법을 정확하게 일치시켜 저장해야 한다.
    • 캐시 사용 방법이 유용하려면 너무 특정 상태에만 치우치게 동작하면 안 된다.
• 두 번째 항목은 Stack Overflow가 발생할 가능성에 관한 것으로, 재귀 호출을 너무 많이 필요로 하는 경우 메모이제이션을 사용하지 못할 수도 있다.
  • 따라서 주어진 문제의 잠재적인 복잡도를 평가하는 작업은 꽤 유용하다.

타뷸레이션: 상향식 접근 방법

• 동적 계획법의 핵심은 메모이제이션과 반대 방식의 접근 방법인 타뷸레이션(tabulation)이라고 할 수 있다.
  • DP라는게 메모이제이션, 타뷸레이션 두 가지 모두에 적용되긴 하지만, 일반적으론 타뷸레이션을 더 많이 의식해서 사용한다고 한다.
• 타뷸레이션은 기저 조건 해답부터 시작하여 모든 부분 문제에 대한 해답을 표에 저장한 후 재사용하는 방식이다.
  • 각각의 부분 문제 상태를 재귀적으로 표현할 수 있어야 하기 때문에 메모이제이션 방법보다 개념적으로 더 어렵게 느껴진다.

#include <bits/stdc++.h>
using namespace std;

int Fibonacci(int n) {
    vector<int> DP(n + 1, 0);
    DP[1] = 1;

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

    return DP[n];
}

• 위 피보나치 예제는 상태가 1차원으로 표현되고 n이 1 보다 큰 경우에 항상 수식 F(n) = F(n - 1) + F(n - 2) 하나만을 사용하기 때문에 매우 간단하지만, 많은 DP 문제에서는 상태를 다차원으로 표현해야 하고, 상태 전환 방식을 여러 개의 조건식으로 표현해햐 할 경우도 있다.
• 타뷸레이션 방식의 장점
  • 메모리 사용량 관점에서 매우 효율적이다.
  • 가능한 모든 상태를 기록하는 룩업 테이블을 생성할 수 있다 --> 주어진 문제에 대해 임의의 여러 상태를 참조해야 하는 경우 타뷸레이션이 최선의 방법이 될 수 있다.
• 보통 메모이제이션으로 해결할 수 있는 모든 문제는 타뷸레이션 방식으로 재구성할 수 있으며, 그 반대도 가능하다.

Ref) 코딩테스트를 위한 자료구조와 알고리즘 with C++