다이나믹 프로그래밍

다이나믹 프로그래밍

• 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법
• 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장(배열이나 리스트 사용)하여 다시 계산하지 않도록 함
• 다이나믹 프로그래밍의 구현은 일반적으로 두가지 방식(탑다운과 보텀업)으로 구성
  - 탑다운(메모이제이션) 방식은 하향식이라고도 함 → 재귀함수 사용

  💡 메모이제이션 : 다이나믹 프로그래밍을 구현하는 방법 중 하나
   한 번 계산한 결과를 메모리 공간에 메모 -> 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져옴        

• 보텀업 방식은 상향식이라고도 함 → 반복문 사용

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

1. 최적 부분 구조
   : 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결

2. 중복되는 부분 문제
   : 동일한 작은 문제를 반복적으로 해결

ex) 피보나치 수열

1. 탑다운 다이나믹 프로그래밍 소스코드

	# 한 번 계산된 결과를 메모이제이션하기 위한 리스트 초기화
    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))

2. 보텀업 다이나믹 프로그래밍 소스코드

    # 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
    d = [0] * 100

    # 첫번째 피보나치 수와 두번쨰 피보나치 수는 1
    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])