[알고리즘] 다이나믹 프로그래밍(DP)

부분 문제 나누기

동적 프로그래밍은 한 문제를 여러 문제로 나누어 해결 하는 기법입니다.

처음 동적 프로그래밍(이후 DP)을 접한 분들은 시작부터 막막하실 수 있습니다.
“한 문제를 어떻게 여러 문제로 나눈다는 거지?” 라고 당연히 의문이 생기실 겁니다.

DP 문제는 문제를 어떻게 나눌지 기준부터 정해줘야 풀이 방법이 보입니다.
대표적인 예시가 피보나치 수열이 있습니다.

피보나치 수열은 다음 값을 현재의 값과 이전 값의 합으로 표현된 수열입니다.
즉, f(n) = f(n - 1) + f(n - 2)
혹은 f(n + 3) = f(n + 1) + f(n + 2) 로 표현할 수 있습니다.

위의 수식에서 여러 문제로 나누어 해결 하는 흔적이 보이나요?
이를 코드로 표현하면 다음과 같이 표현할 수 있습니다.

int fibonacci_top_down(int curr)
{
  if(curr == 0) return 0;
  else if(curr == 1) return 1;
  else 
  {
    return fibonacci(curr - 2) + fibonacci(curr - 1);
  }
}

int fibonacci_bottom_up(int goal_index)
{
  int* arr = new int[1 + goal_index];
  arr[0] = 0;
  arr[1] = 1;
  arr[2] = 2;

  for(int curr = 3; curr <= goal_index; ++curr)
  {
    arr[curr] = arr[curr - 2] + arr[curr - 1];
  }

  return arr[goal_index];
}

두 함수의 이름처럼
fibonacci_top_down 는 위에서 아래로 내려가며 해결하고
fibonacci_bottom_up 는 아래에서 위로 올라가며 해결합니다.

이처럼 DP 문제는 전부는 아니지만 대부분 “N번째 ~하는 ~을 구하라” 형식을 사용합니다.
즉, DP 문제는 반복되는 부분을 일반화 해 답에 도달하는 방법이라고도 할 수 있습니다.

재귀적 풀이와 순환적 풀이

재귀적 풀이와 반복문을 통한 순환적 풀이는
연산 시간은 비슷할 수 있지만 사용하는 자원의 양 에서 큰 차이점이 있습니다.

재귀적 풀이는 재귀를 할 때 마다
현재 갖고 있는 데이터를 스택에 저장해두고 새로운 함수로 넘어가 새로운 스택을 할당 받습니다.
재귀되는 수가 몇 번 없다면 큰 문제가 되지 않을 수 있지만
int의 범위인 2억을 넘긴다고 한다면 2억번 스택을 할당받아야 합니다.
이는 다른 프로그램에도 영향을 줄 있습니다.

따라서 가능하다면 순환적 풀이 로 해결하는 것이 중요합니다.
모든 재귀적 풀이는 순환적 풀이로 변환할 수 있지만 변환하는 과정이 복잡할 수 있습니다.

문제 분할 방법

위에서 이름만 불러줬던 Bottom-up, Top-down
2가지의 방식에 대해 설명해보겠습니다.

Top-down(하향식)

재귀 함수 로 큰 문제를 작은 문제들로 나누어
f(1), f(0)과 같이 가장 작은 문제까지 도달한 뒤
큰 문제를 해결하는 방법이 Top-down 방법입니다.

자주 사용되는 기법으로는 메모이제이션(Memoization) 이 있습니다.
이 기법은 한 번 구현한 결과를 저장해두고 동일한 식을 호출하면
메모한(저장된) 결과를 사용하는 방법으로 중복되는 연산을 제거하여
빠르게 결과를 도출할 수 있습니다.
(메모이제이션 기법은 DP 문제에서만 사용하는 것은 아니다.)

Bottom-up(상향식)

반복문 으로 f(0), f(1) 처럼 작은 문제부터 해결해 나가면서
f(N) 처럼 큰 문제를 해결하는 방법이 Bottom-up 방법입니다.

자주 사용되는 기법으로는 DP 테이블 이 있습니다.
이 기법은 작은 문제에 해당하는 테이블 위치에 연산 결과를 저장합니다.

코드 구현

#include <iostream>

int N, sum = 0;
int* arr = new int[1'001];
int* DP = new int[1'001];

void recursive(int end_index)
{
  DP[end_index] = 1;

  for(int curr = 0; curr < end_index; ++curr)
  {
    if (arr[curr] < arr[end_index])
    {
      DP[end_index] = DP[end_index] > DP[curr] + 1 ? DP[end_index] : DP[curr] + 1;
    }
  }
  sum = DP[end_index] > sum ? DP[end_index] : sum;
  
  if(end_index < N)
  {
    recursive(end_index + 1);
  }
  else
  {
    return;
  }
}

void iterative()
{
  // 수열 전체를 탐색, i는 연속 수열의 마지막 index
  for(int i = 0; i < N; ++i) 
  {
    // 몇 번 연속되는지 DP에 담기 위해 우선 1로 초기화
    DP[i] = 1;

    // 연속수열의 마지막 index i에 닿기 전까지 실행
    // 즉, j는 수열의 시작점에서 시작해 마지막까지 탐색하는 currsor
    for(int j = 0; j < i; ++j) 
    {
      // j번째 원소가 마지막 원소 i보다 작은 경우
      if(arr[j] < arr[i]) 
      {
        // 마지막 원소와 (현재 원소 + 1) 중 큰 값을 대입한다.
        DP[i] = DP[i] > DP[j] + 1 ? DP[i] : DP[j] + 1;
      }
    }
    
    // 마지막 원소에 저장된 최장길이 연속 수열을 sum에 저장한다.
    sum = DP[i] > sum ? DP[i] : sum;
  }
}

// [[BOJ]가장 긴 증가하는 부분 수열] 문제 풀이.
int main() 
{
  cin >> N;
  
  for(int i = 0; i < N; ++i)
  {
    cin >> arr[i];
  }
  
  recursive(0);
  printf("%d", sum);
}   
   

활용 문제

[BOJ] 가장 긴 증가하는 부분 수열
[BOJ] 01타일
[BOJ] LCS
[BOJ] 숨바꼭질
[BOJ] 앱

재귀함수로 금방 구현이 가능했지만, Overflow 상황이 있기 때문에 반복문 DP로 변경
만약, 재귀함수 형식에서 반복문 형식으로 바꿀 때 막막하면 2차원 배열 테이블을 고려해보자.
ex. [N 가지][0 ~ M 까지 합]