Dynamic Programming이란

Dynamic Programming(동적계획법)이란?

큰 문제를 작은 문제로 나누어 푸는 문제를 말한다.

동적 계획법이라는 말 때문에, 어떤 부분에서 동적으로 프로그래밍이 이루어진다고 생각할 수 있지만, 단지 동적 계획법이라는 말이 멋있어서 붙인 이름으로 dynamic이라는 말과 연관이 거의 없다.

 

divide and conquer과 비슷하다고 생각할 수 있지만, 차이점은 작은 문제가 중복이 일어나는지 안 일어나는지이다. divide and conquer는 큰 문제를 해결하기 어려워 작은 문제로 나누어 푸는 방법이다. 특징은, 작은 문제에서 반복이 이렁나지 않는다는 것이다.

 

dynamic programming은 작은 (답이 바뀌지 않는) 부분문제들이 반복되는 것이다.

 

Dynamic Programming 방법

모든 작은 문제들은 한 번만 풀어야 한다. 따라서 정답을 구한 작은 문제를 어딘가에 메모(memorization) 해둔다. 그보다 큰 문제를 풀어갈 때, 똑같은 작은 문제가 나타나면 앞서 메모한 작은 문제의 결과값을 이용한다.

 

Dynamic Programming의 조건

- 작은 문제가 반복이 일어나는 경우

- 같은 문제는 구할 때마다 정답이 같아야 한다

 

위 조건을 만족하는 경우에만 동적 프로그래밍을 사용할 수 있다. 작은 문제의 결과 값이 항상 같다는 점을 이용해서 큰 문제를 해결하는 방법이다.

 

Memorization

동적 프로그래밍에서는 작은 문제들이 반복되고 이 작은 문제들의 결과값이 항상 같다.

이 점을 이용해 한 번 계산한 작은 문제를 저장해놓고 다시 사용한다. 이것을 Memorization이라고 한다.

 

- 예시: 피보나치

(0), 1, 1, 2, 3, 5, 8, ...의 수를 이룬다

다음 수열 = 이전 수열 + 두 단계 전의 수열의 합

 

 

- 재귀 함수 풀이

 

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

 

이미 진행된 fibo(4) 이전의 연산이 반복되는 것을 확인할 수 있다

(fibo(4) 연산 두 번, fibo(3) 연산 세 번 진행)

 

피보나치 수열은 작은 문제들이 반복된다.

그리고, 같은 문제는 구할 때마다 정답이 같다.

첫 번째, 두 번재 수열은 각각 1로 고정되어 있고,

3번째 수열은 언제나 결과가 2이고,

4번째 수열은 3번째 수열과 2번째 수열을 이용해 구하므로 언제나 정답이 같다.

 

 

- 동적 계획법 풀이

 

def memorization_fibo(n):
    memo[0] = 1
    memo[1] = 1
    
    if n < 2:
        return memo[n]
       
    for i in range(2, n + 1):
        memo[i] = memo[i - 2] + memo[i - 1]
    
    return memo[n]
    

memo = [0 for i in range(n + 2)]

 

Bottom-up

- 작은 문제부터 차근차근 구해나가는 방법

 

def fib_bottom_up(n):
    if n <= 1:
        return n
        
    first = 0
    second = 1
    
    for i in range(0, n - 1):
        next = first + second
        first = second
        second = next
    return next

 

Top-down

- 재귀함수로 구현하는 경우가 대부분 Top-down이다

- 큰 문제를 풀때 작은 문제가 아직 풀리지 않았다면 그제서야 작은 문제를 해결한다

 

def fibo_top_down(n):
    if memo[n] > 0:
        return memo[n]
    
    if n <= 1:
        memo[n] = n
        return memo[n]
    
    else:
        memo[n] = fibo_top_down(n - 1) + fibo_top_down(n - 2)
        return memo[n]

memo = [0 for i in range(100)]

 

장단점?

- 딱히 어떤 방법이 좋다고 결정할 수 없다

- Top-down의 경우 소스의 가독성이 증가하는 장점이 있지만, 작성하기 조금 어려운 단점이 있다

- Bottom-up의 경우 코드 작성하기는 쉽지만, 소스의 가독성이 저하될 수도 있다

 

 

 

- 출처: 알고리즘 - Dynamic Programming(동적프로그래밍)이란?