DP

DP (Dynamic Programming)

하나의 문제를 여러개의 작은 문제로 나누어 해결하고 그 결과를 종합하여 정답을 구하는 알고리즘. 

 

접근 방법

• 상향식 접근법(Bottom-Up)
  • 작은 하위문제부터 시작해 큰 문제까지 차근차근 해결하는 방식
  • 작은 문제들을 해결하고 결과를 저장한 후 그 결과를 이용해 보다 큰 문제를 해결함
  • 보통 반복문을 이용해 구현함
• 하향식 접근법(Top-Down)
  • 큰 문제를 작은 하위 문제들로 재귀적으로 나누어 해결하는 방식
  • 재귀적인 호출을 이용해 작은 문제를 해결하고 그 결과를 이용해 큰 문제를 해결함
  • 일반적으로 메모이제이션(Memoization, 결과를 구하고 나중에 다시 활용함) 기법을 사용해 중복 계산을 피함

 

예시) 피보나치

1 재귀로 구현

def fibonacci(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)

 

2 피보나치 함수의 점화식을 DP로 표현

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

 

3 재귀(첫번째)에 메모이제이션 추가

memo = {}
def fibonacci_mem(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    if n in memo:
        return memo[n]
    # 결과값 기록하기!
    memo[n] = fibonacci_mem(n - 1) + fibonacci_mem(n - 2)
    return memo[n]