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

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

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

 

1.1 Divide and Conquer(분할정복)과 비슷한데요?

네, 거의 비슷하지만 결정적인 차이점이 있습니다. 바로 작은 문제가 중복이 일어나는지 안일어나는지 입니다. 분할정복은 큰 문제를 해결하기 어려워 단지 작은 문제로 나누어 푸는 방법입니다. 특징은 작은 문제에서 반복이 일어나는 부분이 없다는 점입니다. 동적프로그래밍은 어떨까요? 네, 작은 부분문제들이 반복되는 것(답이 바뀌지 않음)을 이용해 풀어나가는 방법입니다.

 

1.2 Dynamic Programming 방법

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

 

 

1.3 Dynamic Programming의 조건

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

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

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

 

 

1.4 Memoization?

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

 

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

 

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

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

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

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

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

 

​x
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번째 수열을 구하게 됩니다.

 

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

 

---

 

 

2. Bottom-up 과 Top-down

 

2.1 구현방법

1. Bottom-up

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

xxxxxxxxxx
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이라고 생각하면 됩니다. 큰 문제를 풀 때 작은문제가 아직 풀리지 않았다면 그제서야 작은 문제를 해결하게됩니다.

xxxxxxxxxx
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))    

 

 

2.2 Top down이 좋을까요 Bottom up이 좋을까요?..

아쉽게도 이 질문에는 정답이 없다고 합니다. Top-down의 경우는 소스의 가독성이 증가되는 장점이 있습니다. 하지만 작성하기 조금 어려운 단점이 있습니다. Bottom-up의 경우는 풀기는 쉽지만 소스의 가독성이 저하될 수도? 있습니다. 때문에 자신의 편한 방법으로 풀어나가면 됩니다!

 

 

2.3 Bottom-up과 Top-down 둘중 하나로만 풀리는 경우가 있나요?..

네.. 있습니다. 하지만 저의 실력으로는 아직 그런 문제는 만나보지 못했습니다. 열심히 풀다가 그런 문제를 만날 즈음에는 Bottom-up, Top-down 모두 실력이 출중하여 골라서 풀 수 있지 않을까요?..

 

 

---

팁이 있나요?

저도 아직 알고리즘 초보라 팁이라기는 뭐하지만 제가 DP를 풀면서 느꼇던 것을 말씀 드리겠습니다. 어떤 큰 문제가 있을때 그것의 가장 작은 문제부터 생각합니다. dp[0],dp[1],dp[2],dp[3] 이렇게 작은 문제를 해결하다 보면 규칙을 발견하게 됩니다. 때문에 dp[4]를 해결할 때 즈음에는 이전에 구해놓은 작은 문제들인 dp[0],dp[1],dp[2],dp[3]을 이용해 점화식을 도출해낼 수 있습니다.

 

 

요약

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

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