Dynamic Programming (동적 계획법)

정의

최적해를 구하기 위해 매우 많은 시간이 필요한 경우 연산 결과를 저장하여 중복 연산을 방지함으로써 시간 효율성을 높이는 기법을 말한다.

간단히 말하자면 한 문제를 무조건 한 번만 풀도록 결과를 저장해 사용한다는 것이다.

사용법

언제 사용하는가

• 큰 문제를 작은 문제(큰 문제의 분할)로 나눌 수 있는 경우

  • 작은 문제와 큰 문제의 해결 로직이 같아야 함

• 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일

  • 해결 로직이 순수함수(동일 입력에 반드시 동일 출력이 보장)에 해당해야 함

어떻게 저장하는가

위 조건을 만족하는 문제들의 연산 결과들은 수열에 해당한다고 볼 수 있다.

수열은 규칙적으로 배열된 숫자들의 모임이기 때문에 배열(리스트)에 저장한다.

분할 정복 알고리즘과의 차이

분할 정복 알고리즘이란 퀵 소트와 같이 문제를 분할해 해결하는 기법을 말한다.

다이나믹 프로그래밍과 분할 정복은 문제를 작은 문제로 쪼갠다는 점에서는 동일하나, 분할하여 해결된 작은 문제가 다른 문제의 해결에 영향을 미치는 다이나믹 프로그래밍과 달리 분할 정복에서는 해결된 문제가 다른 문제에 영향을 미치지 않는다.

구현 - Top-Down 방식

큰 문제를 해결하기 위해 작은 문제를 호출

재귀 함수와 메모이제이션(캐싱)을 이용한다.

예시 - Top-Down 방식을 이용한 피보나치 수열 구현

MAX = 100
dp = [0] * MAX

def fibonacci(x):
    if x == 1 or x == 2:
        return 1
    if dp[x] != 0:
        return d[x]
    dp[x] = fibonacci(x - 1) + fibonacci(x - 2)
    return dp[x]

print(fibonacci(MAX - 1))

메모이제이션은 중복 계산을 방지하기 위해 값을 저장하는 것이며, 저장된 연산 결과를 사용하지 않을 수도 있다.

이는 다이나믹 프로그래밍과는 별개의 기법으로 분류된다. 즉, Top-Down 방식은 엄밀히 말하자면 DP에 포함되지는 않는다.

구현 - Bottom-Up 방식

작은 문제부터 차근차근 답을 호출해 큰 문제를 해결

반복문과 DP 테이블을 이용한다.

예시 - Bottom-Up 방식을 이용한 피보나치 수열 구현

MAX = 99
dp = [0] * (MAX + 1)  # DP 테이블

dp[1] = 1
dp[2] = 1
for i in range(3, MAX + 1):
    dp[i] = dp[i - 1] + dp[i - 2]

print(dp[MAX])

전형적인 DP는 Bottom-Up 방식을 말한다. 작은 문제를 해결하고, 이로부터 도출된 값을 통해 큰 문제를 해결하는 방식이다.

다이나믹 프로그래밍을 사용하는 유형

수열화할 수 있는 문제

• 문제를 분할해서 해결할 수 있고, 이렇게 해결한 문제의 일부분이 다른 일부분의 해결에 영향을 미친다면 여기에서 규칙성을 찾아 수열로 나타낼 수 있다.

• 이렇게 수열로 나타낸다면 가장 작은 수부터 차례대로 채워나가는 Bottom-Up 방식을 적용해 다이나믹 프로그래밍 문제로 변환할 수 있다.

• 구현 문제에서도 로직을 수식화하는 문제가 많아 구현 + DP 문제가 많은 것 같다.