09 - Dynamic Programming

Dynamic Programming(동적계획법)이란

큰 문제를 작은문제로 나누어 푸는 문제를 일컫는 말이다. 동적 계획법이란 말 때문에 어떤 부분에서 동적으로 프로그래밍이 이루어지는 찾아볼 필요가 없다. 바로 동적프로그래밍이란 말을 창조한 사람도 이것이 단지 멋있어서 부여한 이름이라고 한다.

 

Divide and Conquer(분할정복)과 비슷해보이는 알고리즘이지만, 결정적인 차이점이 있다 바로 "작은 문제가 중복이 일어나는지 안일어나는지" 이다. 분할정복은 큰 문제를 해결하기 어려워 단지 작은 문제로 나누어 푸는 방법이다.특징은 작은 문제에서 반복이 일어나는 부분이 없다는 점이다. 동적프로그래밍은 작은 부분들이 반복되는것(답이 바뀌지 않음)을 이용해 풀어나가는 방법이다.

 

Dynamic Programming 방법

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

 

Dynamic Programming 조건

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

- 같은 문제는 구할 때 마다 정답이 같다.

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

 

Memoization

메모이제이션은 앞서 말했듯 동적 프로그래밍에서는 작은 문제들이 반복되고 이 작은 문제들의 결과값이 항상 같다. 때문에 이점을 이용하여 한번 계산한 작은 문제를 저장해놓고 다시 사용을 한다. 이것을 Memoization 이라고 한다.

 

피보나치를 예로 들겠다. 피보나치는 1,1,2,3,5,8 ... 의 수를 이루게 된다. 즉, 다음수열 = 이전 수열 + 두단계 전 수열의 합이라는 점화식을 갖는 순열이다. 재귀함수로 풀게되면 이보다도 훨씬 간단하게 풀 수 있지만 n이 증가함에 따라 호출되는 함수의 수가 기하급수 적으로 증가하기 때문에 일정 수 이상의 순열을 구하기가 어렵다.

또한 이렇게 피보나치를 재귀함수로 풀게될 경우, 위의 그림처럼 했던 작업을 또 하게 된다. 이럴 때 위에서 살펴본 동적계획법의 조건 두가지를 상기해보면 이를 동적계획법을 이용해 풀 수 있다는 사실을 알 수 있다.

 

1. 작은 문제들이 반복된다.

F(5)를 구하기 위해서는 F(4), F(3)이 필요하다. 다시 F(4)를 구하기 위해서는 F(3),F(2)가 필요하다. 이 경우를 살펴보면 F(5)에서도 F(3)이 필요하고 F(4)에서도 F(3)이 필요함을 알 수 있다. 즉, 작은 문제가 반복되는 구조이다.

2. 같은 문제는 구할때 마다 정답이 같다.

피보나치 수열의 경우 첫번째 두번째 수열은 각각 1로 고정되어 있다.(편의상 0번째 향이 0이 되는 경우도 있다.)즉 3번째 수열은 언제나 결과가 2이다. 또 4번째 수열은 3번째 수열과 2번째 수열을 이용해 구하므로 언제나 정답이 같다는 사실을 알 수 있다.

def memoization_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]
    
if __name__ == '__main__':
	n = int(sys.stdin.readline())
    memo = [0 for i in range(n+2)]
    print(memoization_fibo(n))

 

n번째 Fibonacci 수열을 구하는 문제를 동적 프로그래밍으로 푼 코드다. 0,1번째 수열은 항상 1이므로 배열에 미리 저장한다. 그 후 2번째 수열을 구할때에는 배열에 저장된 이 값을 이용한다. 구한 2번째 수열의 결과 값을 배열에 다시 저장한다. 그런식으로 진행하며 입력받은 n번째 수열을 구하게 된다.

* 항상 배열을 이용할 때에는 인덱스를 주의해야 한다.

---

Bottom-up & Top down

1. Bottom-up

Bottom-up의 경우 작은 문제부터 차근차근 구해나아가는 방법이다.

def fibonacci_bottom_up(n):
	if n <= 1:
    	return n
   
    fir = 0
    sec = 1
    for i in range(0, n-1):
    	next = fir+sec
        fir = sec
        sec = next
    return next

if __name__ == '__main__':
	n = int(sys.stdin.readline())
    print(fibonacci_bottom_up(n))

2. Top-down

재귀함수로 구현하는 경우가 대부분 Top-down 이라고 생각하면 된다. 큰 문제를 풀 때 작은문제가 아직 풀리지 않았다면 그제서야 작은 문제를 해결하게 된다.

def fibonacci_top_down(n):
		if memo[n] > 0:
        	return memo[n]
        
        if n <= 1:
        	memo[n] = n
            return memo[n]
        
        else:
        	memo[n] = fibonacci_top_down(n-1) + fibonacci_top_down(n-2)
            return memo[n]
            
if __name__ == '__main__':
	memo = [0 for i in range (100)]
    n = int(sys.stdin.readline())
    print(fibonacci_top_down(n))

 

요약 

1. DP는 큰 문제를 작은 문제들로 분할하여 그것을 이용해 큰 문제를 해결하는 방법이다.

2. 분할정복과 다른점은 DP의 경우 작은 부분 문제의 답이 항상 같아야 한다는 것이다.