7. 동적 계획법

동적 계획법

탐욕 기법과 같이 최적화 문제(최대나 최소를 찾는)를 해결하는 알고리즘

• 완전검색을 좀 더 효율적으로 하는 방법
• 재귀 + 메모이제이션
• 점화식을 찾으면 됨!!
• 작은 부분 문제들의 해들을 구함 > 해를 이용하여 보다 큰 크기의 부분 문제들 해결 > 최종적으로 문제 해결

동적 계획법 적용 문제의 요건

• 중복 부분문제 구조
• 최적 부분문제 구조
• 부분 문제들 사이에 의존적 관계가 존재

분할 정복과의 차이점

---

피보나치 수열에 DP 적용

피보나치 수열은 부분 문제의 답으로부터 본 문제의 답을 얻을 수 있으므로 최적 부분 구조로 이루어져 있음

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

알고리즘

def fibo_dp(n):
    f[0] = 0
    f[1] = 1
    for i in range(2, n+1):
        f[i] = f[i-1] + f[i-2]
    return f[n]

 

동전 거스름돈 문제

사용할 수 있는 동전의 종류가 1원, 4원, 6원일 때, 8원에 대한 최소 동전 개수는?

최적해 : 4원, 4원

탐욕 기법의 접근 : 6원, 1원, 1원

→ 탐욕 기법이 항상 최적해를 구할 수 없기 때문에 다른 방법 적용

→ 완전 검색 방법, 동적 계획법

 

재귀적인 알고리즘

3가지 동전 각각을 선택해서 재귀적으로 해결한다.
아래 3가지 중 최적해를 선택

1. 1원 동전 한 개 + 7원에 대한 최적해
2. 4원 동전 한 개 + 4원에 대한 최적해
3. 6원 동전 한 개 + 2원에 대한 최적해

재귀 + 메모이제이션 알고리즘

# change : 거스름돈 금액, coin = [6, 4, 1]: 동전 종류
# memo : 이미 구한 부분 문제의 해를 저장, -1로 초기화
# -1로 초기화되어 있기 때문에 min+1하면 0

def CoinChange(change):
    if memo[change] != -1:
        return memo[change]
    else:
        min = Inf
        for i in range(len(coin)):
            if change - coin[i] >= 0:
                ret = CoinChange(change = coin[i])
                if min > ret:
                    min = ret
        memo[change] = min+1   # 동전개수
        return memo[change]

 

동적 계획법 (상향식)

# change : 거스름돈 금액, coin = [6, 4, 1]: 동전 종류
# memo : 이미 구한 부분 문제의 해를 저장
# 0원에 대한 값은 0으로 초기화하고 시작

def CoinChange_DP(change):
    for N in range(1, change+1):
        min = Inf
        for i in range(len(coin)):
            if N >= coin[i]:
                ret = memo[N-coin[i]]
                if min > ret:
                    min = ret
        memo[N] = min+1
    return memo[change]