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

다이나믹 프로그래밍의 사용 조건

1. 최적 부분 구조: 큰 문제를 작은 문제로 나눌 수 있다.(분할 정복{퀵 정렬} 의 특징이기도 함)

- 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있음.

2. 중복되는 부분 문제: 동일한 작은 문제를 반복적으로 해결한다. (이미 계산한 부분이 또 호출돼서 또 계산되는 것)

- 다이나믹 프로그래밍 문제에서는 각 부분 문제들이 서로 영향을 미치며 부분 문제가 중복된다.

- 분할 정복 문제에서는 동일한 부분 문제가 반복적으로 계산되지 않는다.

다이나믹 프로그래밍의 적용 가능 예

- 피보나치 수열

메모이제이션(Memoization) -> O(N) 시간 복잡도

- 다이나믹 프로그래밍을 구현하는 방법 중 하나(다이나믹 프로그래밍에 국한된 개념 아님!!)

- 한 번 계산한 결과를 메모리 공간에 메모하는 기법

- 이전에 계산된 결과를 일시적으로 기록해 놓는 넓은 개념

- 같은 문제를 다시 호출하면 메모했던 결과가 그대로 불러와 짐

- 값을 기록해 놓는다는 점에서 캐싱(Caching)이라고도 함.

- 결과 저장용 리스트 = DP 테이블

- 탑다운(메모이제이션) 방식은 하향식이라고도 하며 보텀업 방식은 상향식이라고도 한다.

- 저장한 것을 꺼내옴으로써 순차적으로 한 번씩만 실행되기 때문에 O(N)의 시간 복잡도를 보장한다.

# 피보나치 함수를 재귀함수로 구현(탑다운 방식)
d = [0] * 100

def fibo(x):
    # 종료 조건(A1 이나 A2일 경우 반환)
    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))

# 보텀업 방식
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]

print(d[n])