다이나믹 프로그래밍(Dynamic_Programming)

1. Dynamic_Programming 이란

1. 큰문제를 작은 문제로 나눌 때 주로 사용한다.
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일할때 사용할 수 있다.
   주의사항 : 재귀함수로 다이나믹 프로그래밍을 구현시 재귀함수를 적재하는 메모리에서 오버헤드가 발생할수있다.
   따라서 다이나믹 프로그래밍에서는 재귀함수보다 반복문을 사용하여 오버헤드를 줄일 수 있다.

피보나치 수열은 다이나믹 프로그래밍의 대표 문제이다. 파보나치를 통해 다이나믹 함수를 이해해보자.

2. 예시코드(재귀함수 사용)

d = [0] * 100        # 한 번 계산된 결과를 메모이제이션(memoization)하기 위한 리스트 초기화

def fibo(x):         # 피보나치 수열을 재귀함수로 구현(탑 다운 다이나믹 프로그래밍) 
  if x == 1 or x == 2:    # 종료 조건 : x = 1 또는 2일때 1을 반환
    return 1

  if d[x] != 0:      # 만약 d[x]가 0이 아니라면 (= 한번 계산된 문제라면, (피보나치는 f(5) = f(4) + f(3) = (f(3)+f(2)) + (f(2)+f(1)) 이런식으로 쓰였던 f(x)가 계속쓰이기 때문에)) 
    return d[x]      # 계산되었던 값 그대로 반환

  d[x] = fibo(x - 1) + fibo(x - 2)    # 만약 계산된적 없던 값이라면 재귀함수로 피보나치값 반환 (top-down 방식)
  return d[x]

print(fibo(99))

2. 예시코드2(반복문사용)

d = [0] * 100     # 계산된 결과를 담기 위한 리스트로 구하고 싶은 피보나치의 크기

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

for i in range(3, n + 1):     # fibonacci function 반복문으로 구현(bottom-up 방식)
  d[i] = d[i - 1] + d[i - 2]

print(d[n])