[DS&AL] 다이나믹 프로그래밍 (Dynamic Programming, DP)

다이나믹 프로그래밍

다이나믹 프로그래밍은 분할 정복 단계처럼 문제를 풀지만, 하위 문제들에 대한 솔루션들을 결합하면서 문제를 풀어나가는 알고리즘을 말합니다. 즉, 하나의 커다란 문제를 여러 개의 작은 문제로 나누어 그 결과를 저장하고, 다시 큰 문제를 풀 때 사용하는 기법을 통틀어 다이나믹 프로그래밍, DP라고 말합니다. DP라는 것 자체가 어떤 하나의 알고리즘이라기 보다는, 하나의 문제 해결 패러다임이라 할 수 있습니다.

DP를 적용한다면, 메모리 공간을 조금 더 소비하지만 그에 반해 해결 시간을 획기적으로 줄일 수 있습니다.

DP를 사용하기 위해서는 2가지의 조건이 필요합니다. 이 조건들이 충족될 때, DP를 사용하면 유리합니다.

• 최적 부분 구조
  • 문제의 최종 해결 방법은 부분 문제의 최적 문제 해결 방법으로 구성되는데, 이 과정에서 문제 해결의 모든 단계에 대해 해당 단계의 최적 해가 반드시 도출되어야 합니다.
  • 예를 들면, 부분 문제 A에서 B까지 최단 경로 X를 구했을 때, 이 X는 모든 문제에서 최단 경로여야 합니다.
• 중복되는 하위 문제
  • 동일한 작은 문제들이 중복되어 사용되는 경우 사용할 수 있는데, 이 케이스의 경우, 메모이제이션을 사용하여 작은 문제를 재사용할 수 있어야 합니다.

메모이제이션 (Memoization)과 태뷸레이션 (Tabulation)

DP 문제를 풀 때, 크게 메모이제이션 테크닉을 적용하는데, 이는 한 번 계산한 함수(부분 문제)의 결과를 별도의 캐시로 저장해두고, 똑같은 입력이 다시 나오면 계산을 반복하지 않고 저장된 값을 바로 꺼내서 쓰는 것입니다. 이 개념은 밑에 설명드릴 Top-Down 방법에서 주로 사용합니다.

메모이제이션은 크게 다음의 과정으로 적용합니다.

• 값 저장소 변수 준비 : 계산 결과를 저장할 자료 구조를 미리 만들어놓습니다. 이 과정에서 딕셔너리를 사용할 수도 있고, 리스트를 사용할 수도 있습니다.
• 값 확인 : 함수가 호출될 때, 이미 계산된 값이 저장소에 있다면, 그 값을 반환합니다.
• 새로운 값 계산 및 저장 : 저장소에 없는 값은 계산한 후 저장합니다.

Bottom-Up 방식에서는 메모이제이션 대신, 태뷸레이션(Tabulation)이라는 방법을 사용합니다. Tabluation은 도표를 만들어서 값을 채워나가는 방식을 말합니다. 메모이제이션과 정 반대로, 모든 계산 값을 차례대로 진행하며 나아가는 방식을 말합니다.

메모이제이션이 상향식 접근 방법이라면, 태뷸레이션은 하향식 접근 방법입니다.

DP의 구현 스타일

DP의 구현 스타일은 크게 2개, Top-Down, Bottom-Up으로 나뉩니다. 크게 이 2가지 방식으로 문제가 해결된다고 생각하시면 됩니다.

Top-Down

Top-Down 방식은 결과값을 찾기 위해 위에서부터 출발해 제일 작은 문제까지 내려간 다음, 결과값을 재사용해 올라가는 방식을 말합니다. 이미 계산을 완료한 것은 메모이제이션 해두었다가 재사용하여 큰 문제에서 사용합니다.

Bottom-Up

Bottom-Up 방식은 가장 작은 문제로부터 답을 구해 큰 문제를 해결하는 방식을 말합니다. 이 방법은 재귀 호출을 사용하지 않아 메모리 사용량을 줄일 수 있습니다. 여기서는 반복문으로 제일 작은 문제부터 결과를 채워나가는데, 이를 Table Filling이라 합니다.

• 테이블에 저장된 결과를 사용하는 것이 Tabulation입니다.

DP의 적용

DP 방법을 적용해서 문제를 푸는 것에는 크게 다음의 로직으로 진행됩니다.

1. DP로 풀 수 있는 문제인지 확인한다.
   • 현재 직면한 문제가 작은 문제들로 이루어진 하나의 함수로 표현될 수 있는지를 판단
   • 특정 데이터 내 최대화 / 최소화 계산을 하거나 특정 조건 내 데이터를 세야 한다거나 확률 등의 계산의 경우 DP로 풀 수 있는 경우가 많음
2. 문제의 변수 파악
   • 문제 내 변수의 개수를 알아내야 함 → state 결정
3. 변수 간 관계식 만들기 (점화식)
   • 변수들에 의해 결과 값이 달라지지만 동일한 변수값인 경우 결과는 동일
   • 짧은 코드 내에서 반복/재귀를 통해 문제가 자동으로 해결되도록 구축
4. 메모(Memoization or tabulation)
   • 변수 간 관계식까지 정상적으로 생성되었다면 변수의 값에 따른 결과를 저장
   • 변수 값에 따른 결과를 저장할 배열 등을 미리 만들고 그 결과를 나올 때마다 배열 내에 저장하고 그 저장된 값을 재사용하는 방식으로 문제를 해결
5. 기저 상태 파악하기
   • 가장 작은 문제의 상태를 파악해야 함
6. 구현하기
   • Bottom-up
   • Top-down

DP 구현

DP로 수행할 수 있는 가장 대표적인 문제인 피보나치 문제를 Top-Down, Bottom-Up 형식으로 적용한 예시입니다.

## Bottom-Up
def fibo(x):
    memo = [0] * (x+1)
    memo[0] = 1
    memo[1] = 1

    for i in range(2,x+1):
        memo[i] = memo[i-1] + memo[i-2]
    return memo[x]

## Top-Down
memo = [0] * (x+1)
def fibo(x):
  if x == 1 or x == 2:
      return 1
  if memo[x]:
      return memo[x]
  memo[x] = fibo(x - 1) + fibo(x - 2)
  return memo[x]