동적 계획법

: 어떤 문제를 여러개의 작은 문제로 나눠 해결하고 그 결과를 저장했다가 큰 문제를 풀때 사용하는 문제 풀이 기법.

• 분할 정복 알고리즘과 유사하나 해결한 문제를 반복적으로 해결하는 분할 정복과는 달리 동적 계획법은 이미 푼 문제를 기억하여 다시 풀지 않는다.
  
• 해결한 문제를 리스트에 저장하는 것을 Memorization이라 한다.

동적 계획법의 사용 조건

1. 최적 부분 구조

: 문제의 최종 해결 방법은 부분 문제의 최적 문제 해결 방법으로 구성된다. 문제 해결의 모든 단계에서 해당 단계의 최적해가 도출 되어야 한다.

2. 겹치는 부분 문제

: 동일한 작은 문제들이 중복되어 사용되는 경우 사용 가능하다. Memorization을 통해 문제 재사용한다.

동적 계획법 적용 방식

Top-Down

: n의 결과값을 찾기 위해 위에서부터 출발하여 작은 문제까지 내려간 다음에 결과값을 재사용하여 올라가는 방식.

Top-Down 방식의 피보나치 수열

def fibo(n):
    if n == 1 or n == 2:
        return 1
    else: 
        if memorization[n] != 0:
            return memorization[n]
        else:
            memorization[n] = fibo(n-1)+ fibo(n-2)
            return memorization[n]
        
if __name__ == "__main__":
    num = 5
    memorization = [0] * (num+1)
    print(fibo(num))

Top-Down 과정

Bottom-up

: 가장 작은 문제들로부터 답을 구하여 큰 문제를 해결하는 방식.
재귀 호출을 하지 않기 때문에 시간과 메모리 사용량을 줄일 수 있다.

• Table Filling : 반복문을 통해 제일 작은 문제부터 결과 채워 나가는 과정
• Tabulation : 테이블에 저장된 결과를 사용하는 것을

Bottom-Up 방식의 피보나치 수열

if __name__ == "__main__":
    num = 5
    dp = [0] * (num +1)
    dp[1] =1
    dp[2] =1

    for i in range(3, num+1):
        dp[i] = dp[i-1]+dp[i-2]

    print(dp[num])

Bottom-Up 과정