[Advanced] 9. 동적 계획법의 소개 - 이론편

피보나치 수열

0과 1로 시작하고 이전의 두 수 합을 다음 항으로 하는 수열

0, 1, 1, 2, 3, 5, 8, 13, ...

→ f(n+2) = f(n) + f(n+1)

함수 f의 정의로부터 피보나치 수열의 n번째 항을 반환하는 함수를 재귀함수로 구현

def fibo(n):
    if n<2:
        return n
    else:
        return fibo(n-1) + fibo(n-2)

재귀함수로 구현시 문제점 : 엄청난 중복 호출이 발생  !!

 

수학적 귀납법

주어진 식이 n=1일 때 성립함을 증명하고, n일때 성립한다고 가정한 후, n+1일 때 성립함을 증명

 

메모이제이션

컴퓨터 프로그램 실행 시 이전에 계산한 값을 메모리에 저장해서 매번 다시 계산하지 않도록 하여 전체적인 실행속도를 빠르게 하는 기술

동적 계획법의 핵심이 되는 기술

피보나치 수열의 실행시간을 O(n)으로 줄일 수 있음

# memo 리스트를 할당하고, 모두 0으로 초기화한다.
# memo[0]을 0으로, memo[1]을 1로 초기화한다.

def fibo(n):
    if n>=2 and memo[n]==0:
        memo[n] = fibo(n-1) + fibo(n-2)
    return memo[n]

메모이제이션 문제점 : 추가적인 메모리 공간 필요, 재귀함수 호출로 인한 시스템 호출 스택을 사용하게 되고 실행 속도 저하 또는 오버플로우 발생

 

동적 계획법

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

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

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

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

분할 정복과의 차이점

 

피보나치 수열에 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]