Dynamic programming, 기억하며 풀기

 

DP를 번역하면 동적 계획법 이지만

 

책 "컴퓨터 과학이 여는 세계"에서는 다이나믹 프로그래밍을 본질적인 의미를 더 살려서 기억하며 풀기로 더욱 적절하게 번역하였다.

즉, 이전에 구한 작은 부분 문제의 답을, 다음 문제를 푸는데 이용하는 문제 해결 방식. 이전 답을 재활용하면서 더 큰 문제를 해결하는 방식이다.

 

피보나치 수열 구하기(그냥 일반항에 대입하면 나오기는 하지만) 처럼 최종 결과를 도출하기 위해서 이를 더 작은 단위의 문제로 나눠서 먼저 해결하고 그것을 조합하여 최종 문제를 해결하는 방법을 말한다.

 

* 분할 정복과 비슷하나, 분할 정복은 분할된 문제가 서로 영향을 주지 않아 독립적으로 해결 가능하다는 차이점이 있다.

 

진행 방식에 따라 Top-down(Memoization)과 Bottom-up으로 나뉜다.

2017/06/02 - [Web/Front-end] - [JS] memoization, currying

 

Buttom-up 방식의 fibonacci 수열 구하기 (iterative)

def fib(n):
    arr = [0] * (n + 2)
    arr[1] = 1
    arr[2] = 1
    for i in range(3, n+1):
        arr[i] = arr[i-1] + arr[i-2]
    return arr[n]

 

Top-down은 최종 값에서 시작해서 재귀를 통해 끝까지 내려갔다가 resolve하면서 올라오는 방식. (recursive + memo)

Bottom-up은 앞에서 부터 차례차례 구해나가면서 최종 값에 다다르는 방식. (iterative)

 

일단 N+2만큼 array를 잡고 시작하는게 DP 생각하는데 도움이 된다.

 

DP로 풀 때 고려할 점.

일단 메모이제이션쪽으로 사고해서 최종 결과에서 부터 결과 직전의 값으로 타고내려가는 Top-down식을 세운 다음, 이를 Bottom-up 방식으로 고치는 것을 생각해본다.

단, 이 때 약간 직관에서 벗어난, 더 느릴 것 같다는 느낌의 사고를 해야 Bottom-up으로 고칠 수 있는 경우도 종종 있다. 예를 들어 주어진 데이터에 linear하게 접근한다던가...