다이나믹 프로그래밍(Dynamic Programming)이란?

큰 문제를 작게 나누고 같은 문제라면 한 번씩만 풀어(한 번만 계산함) 문제를 효율적으로 해결하는 알고리즘 기법이다.
문제의 답을 구하는 과정에서 점화식을 사용하게 되는 경우 DP 유형으로 볼 수 있다.
메모리 공간을 약간 더 사용하게 되지만 연산 속도를 비약적으로 증가시킬 수 있게 된다.

DP에서 사용되는 두 가지 풀이 방식 with 피보나치 수열

1. top down: 재귀 함수를 이용하여 큰 문제를 해결하기 위해 작은 문제를 호출한다.
같은 문제를 한 번씩만 풀게 되지만 함수를 다시 호출하는 과정이 포함되어 컴퓨터 시스템에서 메모리상에 적재되기 때문에 오버헤드가 발생할 가능성이 크다.
그리고 top down 방식에서는 메모이제이션 기법이 사용된다.

• 메모이제이션 기법이란?
  DP를 구현하는 방법 중 한 종류로서 값을 저장하는 방법으로, 캐싱이라고도 한다.
  한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법이다.
  DP에서 top down 방식에 국한되어 사용되고, 이전에 계산된 결과를 일시적으로 기록해 놓는 넓은 개념으로 DP와는 별도의 개념이다.
  한 번 계산된 결과를 어딘가에 담아놓기만 하고 DP를 위해 활용하지 않을 수도 있다.

피보나치 수열과 함께 top down 방식을 살펴보자.

# top down
d = [0]*100

# 피보나치 수열의 점화식: An+2 = An+1 + An
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]
# 100번째 항 구하기
print(fibo(100))

2. bottom up: 단순히 반복문을 이용하여 작은 문제부터 차근차근 답을 도출한다.
이 방식에서는 오버헤드가 발생하지 않기 때문에 DP는 bottom up 방식으로 해결하는 것이 더 효율적이다.

피보나치 수열과 함께 bottom up 방식을 살펴보자.

# bottom up
d = [0]*101

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

# 피보나치 수열의 점화식: An+2 = An+1 + An
for i in range(3, 101):
    d[i] = d[i-1] + d[i-2]

# 100번째 항 구하기
print(d[100])

DP 유형 접근 방법

문제를 완전 탐색으로 접근했을 때 시간이 매우 오래 걸린다면 DP 유형인지 의심하자.
부분 문제들에서 중복되는 문제들이 존재하는지 확인해서 만약 존재한다면 점화식을 세워 본 후 bottom up 방식으로 문제 해결!
DP는 bottom up으로 해결하는 것이 더 효율적 반드시 bottom up으로 접근하기!

참고 문헌

나동빈,『이것이 취업을 위한 코딩 테스트다』, 한빛미디어(2020), p.208, p.215, p.216