Dynamic Programming

정의

 - 한 번 계산한 결과를 재활용하는 방식

 

구성요소

1. 최적 부분 구조(Optimal Substructure)

 - 부분 문제들의 최적의 답을 이용해서 기존 문제의 최적의 답을 구할 수 있다는 뜻

   ex) 피보나치

2. 중복되는 부분 문제(Overlapping Subproblems)

 - 중복되는 부분 문제를 여러번 계산하는것, 비효율적

 

어떤문제를 해결할 때 1,2번이 존재한다면 Dynamic Programming 으로 문제 해결이 가능!

 

구현

1. Memoization(재귀)

 - Top-down Approach(하향식 접근)

 - 중복되는 계산은 한번만 계산 후 메모

 - Cache에 저장하는 구조

   ex) 피보나치에서 각각의 결과값을 cache에 저장

def fib_memo(n, cache):
	#basecase
    if n == 1 or n == 2:
        return 1
    
    if n in cache:
        return cache[n]
    
    cache[n] = fib_memo(n - 1, cache) + fib_memo(n - 2, cache)
    
    return cache[n]

def fib(n):
    # n번째 피보나치 수를 담는 사전
    fib_cache = {}
    
    return fib_memo(n, fib_cache)


# 테스트 코드
print(fib(10))

2. Tabulation(반복문)

 - Bottom-up Approach(상향식 접근)

 - Table 방식으로 정리한다는 뜻, 문제를 해결하면서 테이블의 내용을 채워나감

n	1	2	3	4	5	6
fib(x)	1	1	2	3	5	8

def fib_tab(n):
    fib = []
    for i in range(n + 1):
        fib.append(0)
    fib[1] = 1
    fib[2] = 1
    
    for i in range(3, n + 1):
        fib[i] = fib[i - 1] + fib[i - 2]
        
    return fib[n]

# 테스트 코드
print(fib_tab(10))

 

피보나치 수열 공간 최적화

def fib_optimized(n):
    current = 1
    previous = 1
    fib = 0
    
    for i in range(3, n + 1):
        fib = previous + current
        previous = current
        current = fib
    
    return fib


# 테스트 코드
print(fib_optimized(16))