동적 계획법 (DP)

[동적 계획법 : DP (Dynamic Programming)]

➡️ 복잡한 문제를 여러 개의 간단한 문제로 분리하여 부분의 문제들을 해결함으로써 최종적으로                     복잡한 문제의 답을 구하는 방법이다. 또한 복잡한 문제를 더 작은 하위 문제로 나누고 이러한 하위           문제에 대한 해를 저장하여 중복 계산을 피함으로써 문제를 해결하는데 사용되는 최적화 기법이다

 

[동적 계획법의 원리와 구현 방식]

1) 큰 문제를 작은 문제로 나눌 수 있어야 한다.

2) 작은 문제들이 반복돼 나타나고 사용되며 이 작은 문제들의 결괏값은 항상 같아야함.

3) 모든 작은 문제들은 한 번만 계산해 DP 테이블에 저장하며 추후 재사용할 때는 이 DP 테이블을 이용한다.

   ➡️ 메모이제이션 (memoization) 기법

4) 동적 계획법은 탑 다운 (Top - Down) 방식과 바텀 업 (Bottom - up) 방식으로 구현한다.

 

[피보나치 수열 (DP의 대표적인 문제)]

P[n] = P[n-1] + P[n-2]

 

#피보나치 수열 함수로 코드 구현하기 ➡️ 입력 값 n의 수열 값 출력

def fibo(n):
    if n == 1:
        return 1
    elif n == 2:
        return 1
    else:
        return fibo(n-1) + fibo(n-2)
    
n = int(input())
print(fibo(n))


def fibo_rec(n):
    if n <= 1:
        return 1
    
    return fibo_rec(n-1) + fibo_rec(n-2)

n = int(input())
print(fibo_rec(n))


def fibo_linear(n):
    f = [0,1]

    for i in range(2, n+1):
        f.append(f[i-1] + f[i-2])

    return f[n]

n = int(input())
print(fibo_linear(n))
    
def fibo_dp(n, memo = {}):
    if n in memo:
        return memo[n]
    
    if n <= 1:
        return n
    
    result = fibo_dp(n-1, memo) + fibo_dp(n-2, memo)
    memo[n] = result
    return result
    
n = int(input())
print(fibo_linear(n))

메모제이션 원리 이해

메모제이션 원리

탑 다운 구현 방식

➡️주로 재귀 함수 형태로 구현

import sys
input = sys.stdin.readline
n = int(input())
d = [-1] 8 (n+1)

d[0] = 0
d[1] = 1

def fibo(x):
	if d[x] != -1:
    	return d[x]
        
    d[x] = fibo(x-2) + fibo(x-1)
    return d[x]
    
fibo(n)
print(d[n])

 

바텀 업 구현 방식

➡️주로 반복문의 형태로 구현

import sys
input = sys.stdin.readlinen
n = int(input())
d = [-1] * (n+1)

d[0] = 0
d[1] = 1

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

print(d[n])