동적계획법 (Dynamic Programming)

동적계획법 (Dynamic Programming)

동적계획법은 문제의 최적해를 구하거나 답의 개수를 세는 과정에 사용할 수 있는 알고리즘이다. 동적계획법을 사용하면 불필요한 계산을 줄이고, 효율적으로 최적의 해를 찾을 수 있다.

동적계획법은 전체 문제를 작은 문제로 단순화한 다음 점화식으로 만들어 재귀적인 구조를 활용해서 해결하는 방식 이다.

ex) sum(n) = 1 + 2 + 3 + ······ + n

​ ⑴ sum(n) = ( 1 + ······ + n-1 ) + n

​ ⑵ sum(n) = sum(n-1) + n

재귀 호출이 가능한 형태로 점화식을 만들고,

값을 리스트로 저장해서 재사용한다.(메모이제이션)

메모이제이션 : 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법

피보나치 수열

• 피보나치 함수를 재귀함수로 구현(Top-down 방식)

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

def fibo(x):
    if x == 1 and x == 2:
        return 1
    # 이미 계산한 적 있는 문제라면 그대로 반환
    if d[x] != 0:
        return d[x]
    d[x] = fibo(x - 1) + fibo(x - 2)
    return d[x]

print(d[n])

• 피보나치 함수를 반복문으로 구현(Bottom-up 방식)

d = [0] * 100
d[1] = 1
d[2] = 1
n = 99

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