[Algorithm] Dynamic Programming

Dynamic Programming (동적 계획법)

DP, Dynamic Programming(또는 동적 계획법)은 기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것으로 특정한 알고리즘이 아닌 하나의 문제해결 패러다임으로 볼 수 있습니다.

동적 계획법이란 말 때문에 어떤 부분에서 동적으로 프로그래밍이 이루어지는 지 찾아볼 필요 없습니다. 동적 프로그래밍 이란 말을 창조한 사람도 이것이 단지 멋있어서 부여한 이름이라고 합니다.

DP 를 사용하는 이유

사실 일반적인 재귀(Naive Recursion) 방식 또한 DP와 매우 유사합니다. 큰 차이점은 일반적인 재귀는 사용 시 동일한 작은 문제들이 여러 번 반복 되어 비효율적인 계산될 수 있다는 것입니다.

예를 들어 피보나치 수열을 살펴보겠습니다.
ex. 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89...

피보나치 수를 구하고 싶을 때 재귀함수로 구성하면 다음과 같습니다.

int fibo(int n)
  {
    if (n<=2)
      return 1;
    else
      return fibo(n-1) + fibo(n-2);
   }

f(n-1), f(n-2)에서 각 함수를 1번씩 호출하면 동일한 값을 2번씩 구하게 되고 이로 인해 100번째 피보나치 수를 구하기 위해 호출되는 함수의 횟수는 기하급수 적으로 증가하게 됩니다.
그러나 한 번 구한 작은 문제의 결과 값을 저장해두고 재사용 한다면 앞에서 계산된 값을 다시 반복할 필요가 없이 매우 효율적으로 문제를 해결할 수 있게 됩니다.

DP 원리

DP에서는 모든 작은 문제들을 한 번만 풀어야 합니다. 그렇기 때문에 정답을 구한 작은 문제의 답은 어딘가에 메모해놓습니다. 그리고 그 보다 더 큰 문제를 풀어나갈 때, 똑같은 작은 문제가 나타나면 앞서 메모한 작은 문제에 대한 결과값을 이용합니다.
가장 작은 부분의 해답을 구한 뒤 이를 저장하고, 저장한 값을 이용하여 상위 문제를 풀어가는 방식이라고 할 수 있습니다. 이때 Memoization(메모이제이션) 이라는 기법으로 중복된 계산을 줄일 수 있습니다.

DP 사용 조건

• Overlapping Subproblems(부분 반복 문제)
• Optimal Substructure(최적 부분 구조)

Overlapping Subproblems(부분 반복 문제)

위의 경우에서 7번째 값을 구하기 위해서는 총 25번의 함수가 호출됩니다. 이 과정에서 fibo(5), fibo(4), fibo(3)들이 이미 진행했던 연산임에도 불구하고 재귀되며 반복적으로 연산하는 것을 볼 수 있습니다.
이러한 반복적인 연산을 부분 반복 문제라고 합니다. 이는 어떤 문제가 여러 개의 부분 문제로 쪼개질 수 있을 때 사용하는 용어입니다.

Optimal Substructure(최적 부분 구조)

최적 부분 구조란, 작은 부분 문제에서 구한 최적의 답으로 합쳐진 큰 문제의 최적의 답을 구할 수 있어야 한다는 것을 말합니다.

fibo(n) = fibo(n-1) + fibo(n-2)

여기서 큰 문제의 답인 fibo(n) 이 최적의 답이 되려면, 작은 부분의 문제인 fibo(n-1), fibo(n-2)이 최적의 답이어야만 합니다.

여기서, fibo(n-1)을 구하기 위해서는 다시 fibo(n-2) + fibo(n-3)이 되고, fibo(n-2)가 중복되게 됩니다. 그리고 최적 부분 구조를 만족한다면 문제의 크기에 상관없이 fibo(n-1)은 언제나 일정한 값을 가집니다.

Memoization (메모이제이션)

위의 중복되는 연산과정을 해결하기 위해 Memoization 이라는 기법이 도입되었습니다. 동적 프로그래밍에서는 작은 문제들이 반복되고 이 작은 문제들의 결과값이 항상 같습니다. 때문에 이점을 이용하여 한번 계산한 작은 문제를 저장 해놓고 다시 사용합니다. 이것을 Memoization 이라고 합니다.

DP 구현 방법

• Bottom-Up (Tabulation 방식) - 반복문 사용
• Top-Down (Memoization 방식) - 재귀 사용

Bottom-Up (Tabulation 방식)

가장 작은 문제들부터 답을 구해가며 이를 누적시켜서 전체 큰 문제를 해결하는 방식입니다. Bottom-up 일 때는 Tabulation 방식이라고도 부릅니다.

반복을 통해 dp[0]부터 하나 하나씩 채우는 과정을 "table-filling" 하며, 이 Table에 저장된 값에 직접 접근하여 재활용하므로 Tabulation이라는 명칭이 붙었습니다.

# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
dp = [0] * 101
dp[1] = 1
dp[2] = 1
n = 100

# 피보나치 수열 반복문으로 구현(Bottom-Up DP)
for i in range(3, n + 1):
    dp[i] = dp[i - 1] + dp[i - 2]

print(dp[n])

Top-Down (Memoization 방식)

재귀함수로 구현하는 경우가 대부분 Top-down이라고 생각하면 됩니다. 큰 문제를 풀 때 작은문제가 아직 풀리지 않았다면 그때 작은 문제를 해결하게 됩니다.

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

# 메모이제이션하기 위한 리스트 초기화
memoization = [0] * 101

# 피보나치 함수를 재귀함수로 구현 (Top-down DP)
def fibo(x):
    if x == 1 or x == 2:
        return 1
    # 이미 계산한 적 있으면 그대로 반환
    if memoization[x] != 0:
        return memoization[x]
    # 계산한 적 없으면 점화식에 따라 피보나치 결과 반환
    memoization[x] = fibo(x - 1) + fibo(x - 2)
    return memoization[x]

print(fibo(n))

Q. Divide and Conquer(분할 정복)와 차이점?

분할 정복과 동적 프로그래밍은 주어진 문제를 작게 쪼개서 하위 문제로 해결하고 연계적으로 큰 문제를 해결한다는 점은 같지만 분할 정복은 분할된 하위 문제가 동일하게 중복이 일어나지 않는 경우에 쓰며, 동일한 중복이 일어날때 동적 프로그래밍을 사용해줍니다.