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

동적 계획법(Dynamic Programming)이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 특정한 알고리즘이 아닌 하나의 문제 해결 패러다임으로 볼 수 있다.

 

Dynamic Programming의 조건

1. 분할 가능
   큰 문제를 작은 문제로 나눌 수 있을 때 (Problem → Subproblems)
2. 부분 문제 반복(Overlapping Subproblems)
   Subproblem들이 겹칠 때 → memoization을 통해 필요한 연산 수를 줄일 수 있음
3. 최적 부분 구조(Optimal Substructure)
   Subproblems의 Solution으로 더 큰 규모의 Problem의 Solution을 구할 수 있을 때

 

대표 문제 : 피보나치 수열 Fibonacci

📌 Naive Recursion

# naive fibonacci
def fib_naive(n):
    if n==0:
        return 0
    elif n==1:
        return 1
    else:
        return fib_naive(n-1)+fib_naive(n-2)

📌 Recursive Dynamic Programing

👇 Top Down

# Top Down
fib_arry = [0,1]
def fib_recur_dp(n):    
    cnrt_length = len(fib_arry)
    if n < cnrt_length:
        return fib_arry[n] 
    else:
        fib = fib_recur_dp(n-1)+fib_recur_dp(n-2)
        fib_arry.append(fib)
        return fib

👇 Bottom Up

# Bottom Up
def fib_dp(n):
    if n==0:
        return 0
    elif n==1:
        return 1
    fib_array = [0,1]  
    for i in range(2, n+1):        
        num = fib_array[i-1]+fib_array[i-2]
        fib_array.append(num)
    return fib_array[n]

 

Dynamic Programming을 쓰는 이유

일반적인 재귀(Naive Recursion)과 DP는 매우 유사하다. 차이점은 일반적인 재귀를 사용할 때는 동일한 작은 문제들이 여러 번 반복되어 비효율적인 계산이 될 수 있다는 것이다. DP는 Memoization 기법을 통해 반복되는 작은 문제들의 결과 값을 저장해 두고 재사용하여 계산 속도를 향상시킨다.

💡 Memoization(메모이제이션)은 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다.

 

Top Down vs Bottom Up

Memoization을 위해 dp라는 배열을 만들었고 이것이 1차원이라 가정했을 때, dp[0]가 기저 상태이고 dp[n]을 목표 상태라고 하자.

💡 기저 상태 : 가장 작은 문제의 상태를 말한다.
ex) 피보나치 수열의 f(0) = 0, f(1) = 1

📌 Top Down

dp[n]의 값을 찾기 위해 위에서부터 바로 호출을 시작하여 dp[0]의 상태까지 내려간 다음 해당 결과 값을 재귀를 통해 전이시켜 재활용하는 방식이다.

피보나치의 예시처럼, f(n) = f(n-2) + f(n-1)의 과정에서 함수 호출 트리의 과정에서 보이듯, n=5일 때, f(3), f(2)의 동일한 계산이 반복적으로 나오게 된다.

이때, 이미 이전에 계산을 완료한 경우에는 단순히 메모리에 저장되어 있던 내역을 꺼내서 활용하면 된다. 그래서 가장 최근의 상태 값을 메모해 두었다고 하여 Memoization이라고 부른다.

📌 Bottom Up

기저 상태부터 계산을 수행하고 누적시켜 전체 문제를 해결하는 방식이다. dp[0]부터 시작하여 반복문을 통해 점화식으로 결과를 내서 dp[n]까지 그 값을 전이시켜 재활용하는 방식이다.

💡 Tabulation(테뷸레이션)이란?
Bottom Up 방식에서는 Memoization을 Tabulation이라 부른다.
왜냐면 반복을 통해 dp[0]부터 하나하나씩 채우는 과정을 “table-filling”이라 하며, 이 Table에 저장된 값에 직접 접근하여 재활용하므로 Tabulation이라는 명칭이 붙었다고 한다. 사실상 근본적인 개념은 결과값을 기억하고 재활용한다는 측면에서 Memoization과 크게 다르지 않다. 하지만, Memoization은 결과가 필요해질 때 계산한다면(Lazy-Evaluation) Tabulation은 필요하지 않은 값도 미리 계산해둔다(Eager-Evaluation)는 차이가 있다. 따라서 Tabulation은 초기화 오버헤드가 있지만 일단 계산해둔 값은 시간복잡도가 상수 시간(O(1))이 된다.

 

동적 계획법 vs 분할 정복

📌 공통점

• 주어진 문제를 작게 쪼개서 하위 문제로 해결하고 연계적으로 큰 문제를 해결한다.

📌 차이점

• 동적 계획법
  • 부분 문제는 중복되어, 상위 문제 해결 시 재활용된다.
  • Memoization 기법을 사용한다.
  • ex) 피보나치 수열
• 분할 정복
  • 부분 문제는 서로 중복되지 않는다.
  • Memoization 기법을 사용하지 않는다.
  • ex) 병합 정렬, 퀵 정렬

 

📗 참고

• 코딩테스트, 기초, 다이나믹 프로그래밍, dynamic programming
• 알고리즘 - Dynamic Programming(동적 계획법)
• 위키백과 - 메모이제이션