Dynamic Programming

다이나믹 프로그래밍은 동적 계획법이라고 표현하기도 한다.
한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘이다.
메모리 공간을 약간 더 사용하여 연산 속도를 비약적으로 증가시킬 수 있는 방법이다.

1. 재귀 함수 예시

다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예시로 피보나치 수열이 있다.

피보나치 수열은 이전 두 항의 합을 현재의 항으로 설정하는 특징이 있는 수열이다.

• n번째 피보나치 수 = (n - 1)번째 피보나치 수 + (n - 2)번째 피보나치 수
• 단, 1번째 피보나치 수 = 1, 2번째 피보나치 수 = 1

피보나치 함수를 구현하기 위해 가장 쉬운 방법으로 재귀 함수를 사용하면 된다.

def fibo(x):
    if x == 1 or x == 2:
        return 1
    return fibo(x - 1) + fibo(x - 2)

그런데 피보나치 수열을 이렇게 작성하면 fibo(n) 함수에서 n이 커지면 커질수록 수행 시간이 기하급수적으로 늘어난다.

이처럼 피보나치 수열의 점화식을 재귀 함수를 사용해 만들 수는 있지만, 단순히 매번 계산하도록 하면 문제를 효율적으로 해결할 수 없다.

2. 다이나믹 프로그래밍 예시

이러한 문제는 다이나믹 프로그래밍을 사용하면 효율적으로 해결할 수 있다. 다만 항상 다이나믹 프로그래밍을 사용할 수 없으며, 다음 조건을 만족할 때 사용할 수 있다.

• 큰 문제를 작은 문제로 나눌 수 있다.
• 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

2-1. 메모이제이션(Memoization) 기법

다이나믹 프로그래밍을 구현하는 방법 중 한 종류로, 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법을 의미한다.

# Memoization하기 위한 리스트 초기화
d = [0] * 100

def fibo(x):
    if x == 1 or x == 2:
        return 1
    # 이미 계산한 적이 있는 문제라면 그대로 반환
    if d[x] != 0:
        return d[x]
    # 아직 게산하지 않은 문제라면 피보나치 결과 반환
    d[x] = fibo(x - 1) + fibo(x - 2)
    return d[x]

정리하자면 다이나믹 프로그래밍은 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법이다.

2-2. Top-Down, Bottom-Up 방식

재귀 함수를 사용하면 컴퓨터 시스템에서는 함수를 다시 호출했을 때 메모리 상에 적재되는 일련의 과정을 따라야 하므로 오버헤드가 발생할 수 있다. 따라서 재귀 함수 대신에 반복문을 사용하여 오버헤드를 줄일 수 있다.

재귀 함수를 이용하여 다이나믹 프로그래밍 소스를 작성하는 방법을, 큰 문제를 해결하기 위해 작은 문제를 호출한다고 하여 탑다운(Top-Down)방식이라고 말한다. 반면에 단순히 반복문을 이용하여 소스코드를 작성하는 경우 작은 문제부터 차근차근 답을 도출한다고 하여 바텀업(Bottom-Up) 방식이라고 말한다. 피보나치 수열 문제를 아래에서 위로 올라가는 바텀업 방식으로 풀면 다음과 같다.

# 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 100

d[1] = 1
d[2] = 1
n = 99

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

다이나믹 프로그래밍의 전형적인 형태는 바텀업 방식이다. 바텀업 방식에서 사용되는 결과 저장용 리스트는 'DP 테이블' 이라고 부르며, 메모이제이션은 탑다운 방식에 국한되어 사용되는 표현이다.

Reference

• 이것이 코딩 테스트다 with 파이썬 - 나동빈
• 피보나치 이미지