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

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

문제를 각각 작은 문제로 나누어 해결한 후, 그 해를 이용해 큰 크기의 문제들을 해결하여 최종적으로 원래 주어진 입력의 문제를 해결하는 방법

간단히 -> 작은거 부터 해결하고, 그 결과를 이용해 큰거 + 결과까지 다 해결한다

 

 

1. Bottom-Up ( 상향식 ) : 더 작은 하위 문제부터 살펴본 다음, 작은 문제의 정답을 이용해 큰 문제의 정답을 품.

-> 데이터를 테이블 형태로 만들면서 문제를 풀기 때문에 Tabulation이라고 부름 

n = int(input())
dp = [0]*(n + 1)

def fibo(n):
    dp[0] = 0
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]
 
print(fibo(n))

 

 

2. Top-Down ( 하향식 ) : 하위 문제에 대한 정답을 계산했는지 확인해가며 품.

-> Memoization이라 지칭 / 재귀랑 거의 동일

n = int(input())
dp = [0]*(n + 1)

def fibo(n):
    if n <= 1:
        return n
    if dp[n]:
        return dp[n]
    dp[n] = fibo(n - 1) + fibo(n - 2)
    return dp[n]

print(fibo(n))

컴퓨터 프로그램을 실행할 때 이전에 계산한 값을 메모리에 저장해서 매번 다시 계산 하지 않아 실행속도를 빠르게 하는 것이 DP의 핵심이다.

 

 

-> 이제 막 시작단계라 계속 수정하며 내용 추가할 예정