Dynamic Programming

: 큰 문제를 작은 부분 문제로 나누어 해결하는 알고리즘

조건

  1. 최적 부분 구조

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

  2. 중복되는 부분 구조

구현 방법

1. Memoization

: 중복되는 계산을 피하기 위해 이전에 계산한 값을 저장해두는 것

예시) 피보나치 수 - 6번째 피보나치 수를 찾는다고 가정

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

Untitled

<aside> 💡 캐시(Cache): 다시 쓸 값들을 저장해 놓는 공간

</aside>

피보나치 수열을 Memoization 방식으로 구현

: 재귀 함수 사용

def fib_memo(n, cache):
    # base case
    if n < 3:
        return 1
        
    # 이미 n번째 피보나치를 계산했으면:
    # 저장된 값을 바로 리턴한다
    if n in cache:
        return cache[n]
    
    # 아직 n번째 피보나치 수를 계산하지 않았으면:
    # 계산을 한 후 cache에 저장
    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))   # 55
print(fib(50))   # 12586269025
print(fib(100))  # 354224848179261915075

2. Tabulation

: 작은 부분 문제의 해를 계산하여 테이블에 저장하고, 이를 활용하여 큰 문제의 해를 구하는 방법

예시) 피보나치 수 - 6번째 피보나치 수를 찾는다고 가정

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

Untitled

피보나치 수열을 Tabulation 방식으로 구현

: 반복문 사용

def fib_tab(n):
    # 이미 계산된 피보나치 수를 담는 리스트
    fib_table = [0, 1, 1]

    # n번째 피보나치 수까지 리스트를 하나씩 채워 나간다
    for i in range(3, n + 1):
        fib_table.append(fib_table[i - 1] + fib_table[i - 2])

    # 피보나치 n번째 수를 리턴한다
    return fib_table[n]

# 테스트 코드
print(fib_tab(10))   # 55
print(fib_tab(56))   # 225851433717
print(fib_tab(132))  # 1725375039079340637797070384

Memoization vs Tabulation