다이나믹 프로그래밍(Dynamic Programming, 동적 계획법)

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 사용해보면서 배운 점을 정리한 글입니다.

다이나믹 프로그래밍(Dynamic Programming, 동적 계획법)이란?

문제를 작은 문제로 나누어 해결된 결과를 저장한 뒤 나중에 등장할 큰 문제의 해결을 위해 기존 해결해뒀던 결과들을 조합하여 풀이하는 알고리즘이다. 문제의 최적 해결 방법이 부분 문제에 대한 최적 해결 방법으로 구성되는 경우의 문제라면 최적 부분 구조(Optimal Substructure)를 갖는다고 말하는데 해당 속성을 갖는 문제를 풀이할 수 있다. 최적 부분 구조의 문제를 해결하는 알고리즘으로 그리디 알고리즘과 분할 정복이 있는데 그리디 알고리즘은 "매 순간 최적이라 생각되는 답을 선택"하면서 문제를 해결하는 반명 다이나믹 프로그래밍은 "중복된 하위 문제(Overlapping Subproblem)의 결과를 저장"했다가 이후 문제 풀이에 사용한다는 차이점이 있다. 핵심은 "중복된 하위 문제"로 중복되지 않은 하위 문제로 구성되었다면 분할 정복으로 해결한다고 말한다.

그리디는 그 순간의 최적해만 고려한다는 점, 분할 정복은 중복된 하위 문제가 아니므로 단위만 작아졌을 분 답이 매번 달라 매번 해결해야 하는 차이가 있다.

다이나믹 프로그래밍 방법론

동적 계획법 구현에는 2 가지가 있는데 대표적 DP 문제인 피보나치 수열로 예시를 들어보자.

상향식(Bottom-Up) - 타뷸레이션(Tabulation)

더 작은 하위 문제부터 정답을 도출하고 작은 문제의 정답을 이용해 큰 문제의 정답을 도출한다. 타뷸레이션(Tabulation)이라고도 부른다. 불필요할 수 있는 값도 미리 계산하는 특성(Eager-Evaluation)이 있다.

def fibo_tabulation(k):
    dp = [0, 1] # 초기 조건
    for _ in range(k - 1):
        dp.append(dp[-1] + dp[-2]) # 작은 문제의 조합으로 다음 문제 해결
    return dp[k]

result = []
n = 10
for i in range(1, n + 1):
    result.append(fibo_tabulation(i))
print(result)

앞선 작은 문제들을 해결하고 그 결과를 더해 이후의 값을 만드는 모습이다.

하향식(Top-Down) - 메모이제이션(Memoization)

하위 문제의 정답이 도출되었는 지 확인하며 문제를 해결한다. 따라서 재귀함수 형태로 구성된다.

def fibo_memoization(dp, k):
    if k <= 1:
        return k
    if len(dp) > k:
        return dp[k]
    dp.append(fibo_memoization(dp, k - 2) + fibo_memoization(dp, k - 1))
    # 더 작은 문제의 결과값을 재귀호출로 확인
    return dp[k]

result = []
n = 10
for i in range(1, n + 1):
    result.append(fibo_memoization([0, 1], i))
print(result)

메모이제이션은 결국 재귀함수로 더 작은 문제 해결을 위해 호출되기 때문에 함수의 리턴값이나 저장되는 형태를 명확히 해야 한다.