이것이 코테다 영상 강의 - 다이나믹 프로그래밍

다이나믹 프로그래밍 : 메모리를 적절히 사용하여 수행 시간 효율성을 높이는 방법

• 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다.
• 바텀업과 탑다운 2가지가 잇다.
• 동적 계획법이라고도 한다.
• 다이나믹 프로그래밍은 다음 조건을 만족할 때 사용 가능하다.
  • 최적 부분 구조(optimal substucture)
    -> 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다.
  • 중복되는 부분 문제(overlapping subproblem)
    -> 동일한 작은 문제를 반복적으로 해결해야 한다.

• 예를 들어 피보나치 수열을 다이나믹 프로그래밍으로 효과적으로 계산 가능
  • DP를 사용하지 않으면 기하급수적으로 높은 시간 복잡도를 가질 수 있다. -> $O(2^n)$

# 피보나치 수열 단순 재귀
def fibo(x):
    if x == 1 or x == 2:
        return 1
    return fibo(x - 1) + fibo(x - 2)

print(fibo(4))

탑다운(하향식) 기법 : 메모이제이션(memoization)

• 다이나믹 프로그래밍을 구현하는 방법 중 하나
• 한 번 계산한 결과를 메모리 공간에 메모하는 기법
  • 같은 문제 호출 시 메모했던 결과를 그대로 가져온다.
  • 값을 기록해 놓는다는 점에서 캐싱(caching)이라고도 한다.

# 피보나치 수열 : 탑다운 다이나믹 프로그래밍
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))

보텀업(상향식) 기법 : 작은 문제들을 해결하고 저장하고, 큰 문제를 풀 때 사용

• DP의 전형적인 형태이다. -> 결과 저장용 리스트를 DP 테이블이라고 한다.
• 메모이제이션은 DP에만 국한된 개념이 아니다. (그냥 결과를 저장하는 기법이다.)

# 피보나치 수열 : 보텀업
d = [0] * 100

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

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

print(d[n])