8. 다이나믹 프로그래밍

8-1. 다이나믹 프로그래밍

중복되는 연산을 줄이자
컴퓨터를 활용해도 어려운 문제는 시간이 매우 많이 걸리거나, 메모리 공간이 매우 많이 필요한 문제이다.
컴퓨터 연산에는 한계가 있고, 메모리 공간도 데이터 개수가 한정적이다.
그러므로 우리는 연산 속도와 메모리 공간을 최대한으로 활용할 수 있는 알고리즘을 작성해야 한다.
그러나, 어떤 문제는 메모리 공간을 약간 더 사용하면, 연산 속도를 비약적으로 증가시킬 수 있는 방법이 있다.
이것이 다이나믹 프로그래밍이다.

• 탑다운, 바텀업

• 메모이제이션 기법

• 예시) 피보나치 수열

  다이나믹 프로그래밍을 사용할 수 있는 조건은 다음과 같다.

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

 # 피보나치 수열 (메모이제이션)
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]
    
print(fibo(99))

큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 효율적으로 해결하는 알고리즘 기법이다.
사실 퀵 정렬에서도 리스트를 분할하여 전체적으로 정렬이 될 수 있도록 한다.
이는 분할 정복 알고리즘으로 분류된다.

그렇다면 다이나믹 프로그래밍을 적용 했을 때 피보나치 수열 알고리즘 시간 복잡도는 어떻게 될까? $O(N)$이다. (f(1)을 구한 값이 f(2)로, f(2)값이 f(3)을 구하는 데 이용되기 떄문)

• 재귀 함수를 이용하여 DP를 해결 => 탑 다운 방식(하향식)
• 반복문을 이용하여 작은 문제부터 차근 차근 답을 도출 => 보텀 업 방식(상향식)
• 주어진 문제가 DP임을 파악하는 것이 제일 중요하다.
• 시간이 매우 오래 걸리면 DP를 적용할 수 있는지 중복 여부를 확인해보자.
• 단순히 재귀함수로 비효율적인 프로그램을 작성 한 뒤 (탑다운) 작은 문제에서 구한답이 문제에서 그대로 사용될 수 있으면, 즉 메모이제이션을 적용할 수 있으면 개선하자.
• 또한, 보텀업 방식으로 구현하는 것을 권장한다. (시스탬 스택 사이즈)