[알고리즘] Dynamic Programming

DP

메모이제이션(memoization)

• 이전에 계산한 값을 메모리에 저장해서 매번 다시 계산하지 않도록 하여 전체적인 실행속도를 빠르게 하는 기술
  → 동적 계획법의 핵심 기술!
• ex) 피보나치 수열의 재귀: 중복호출을 반복하게 됨

# memo를 위한 배열을 할당하고, 모두 0으로 초기화 한다.
# memo[0]을 0으로 memo[1]은 1로 초기화 한다.

fibo(n)
    IF n>=2 AND memo[n] = 0
        memo[n] <- fibo(n-1) + fibo(n-2)
    RETURN memo[n]

→ 추가적인 메모리 공간이 필요

→ 재귀 함수 호출로 인한 시스템 호출 스택을 사용하게 되고 실행 속도 저하 또는 오버플로우가 발생

동적 계획법

적용 요건

1. 부분 문제들은 더 작은 부분 문제들을 공유한다.
2. 모든 부분 문제를 한번만 계산하고 결과를 저장하고 재사용한다.

피보나치 수 DP 적용

1. 문제를 부분 문제로 분할한다.
2. 점화식으로 정의한다.
3. 가장 작은 부분 문제부터 해를 구한다. 결과를 테이블에 저장하고, 저장된 부분 문제의 해를 이용하여 상위 문제의 해를 구한다.

fibo_dp(n)
    f[0] <- 0
    f[1] <- 1
    for i in 2->n
        f[i] <- f[i-1] + f[i-2]
    return f[n]

→ 중복 계산이 없고 반복문 사용으로 함수 호출이 없기 때문에 수행속도가 더 빠르다!

Knapsack

정의

• W = 배낭의 용량
• ( vi, wi ) = 가치, 무게 물건
• K[i,w] = 물건 1~i까지만 고려하고, 배낭의 용량이 2일 때의 최대 가치

FOR i in 0 -> n : K[i, 0] <- 0
FOR w in 0 -> W : K[0, w] <- 0

FOR i in 1 -> n
    FOR w in 1 -> w
        IF wi > w
            K[i, w] <- K[i-1, 2]
        ELSE
            K[i, w] <- max(vi + K[i-1, w-wi], K[i-1, w])

RETURN K[n,W]