다이나믹 프로그래밍(DP)?
어떤 문제를 풀기 위해 그 문제를 더 작은 문제의 연장선으로 생각하고, 과거에 구한 해를 활용하는 방식의 알고리즘을 이야기 한다.
다이나믹 프로그래밍은 다음의 가정 하에서 사용할 수 있다.
- 큰 문제를 작은 문제로 나눌 수 있다.
- 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.
조금 더 쉽게 피보나치 수열(앞의 두 항의 합이 뒤 항의 값으로 되어있는 수열)을 예를 들어 설명해보겠다.
피보나치 수열의 특정 항의 값을 구하기 위해서는 다음과 같은 재귀 함수를 이용할 수 있다.
10번째 항을 구하기 위해서는 fibo함수를 109번을 호출해야 한다. 코드의 가독성은 좋지만 실제 수행 시간은 굉장히 오래 걸리는 문제가 있다.
다이나믹 프로그래밍을 이용하면 수행시간을 단축시킬 수 있다.
백문이 불여일견이니 먼저 아래 코드를 보도록 하자.
위 코드는 피보나치 수열의 각 항의 값을 배열에 미리 저장해놓는 코드이다. 자세히 살펴보자.
크기가 101개인 배열을 미리 만들어 두었다. 이 배열의 index는 실제 피보나치 수열에서 몇 번째 항인지를 의미한다.
따라서 첫째항과 둘째항에 먼저 1을 넣어주었고 세 번째 항부터는 앞의 두 항의 합을 이용하여 값을 계산해주면 된다.
이렇게 미리 100번째 항까지 계산 결과를 미리 배열에 저장해두면 다음에 같은 연산을 진행할 때는 저장된 값을 반환하기만 하면 되기 때문에 수행시간이 줄어들게 되는 것이다.
위에서 미리 배열에 저장해놓는 것처럼 반복되는 문제들의 결과를 저장하는 것을 메모이제이션(Memoization)이라고 한다. 다이나믹 프로그래밍에서는 메모이제이션이 필수적이라고 생각된다.
Bottom-up & Top-down
- Bottom-up
- 작은 문제부터 차근차근 구해나가는 방법이다.
- 위에서 구현한 방법이 Bottom-up 방식이며 풀기에는 쉽지만 가독성이 조금 좋지 않다는 느낌이 든다.
- Top-down
- 재귀 함수를 이용하여 구현하는 경우가 대부분 Top-down방식이다. 큰 문제를 푸는데 그보다 작은 문제가 풀리지 않았다면 작은 문제를 먼저 풀도록 한다.
- 재귀 함수를 이용하기 때문에 가독성은 좋지만 풀이가 어렵다고 생각이 된다.
읽어주셔서 감사합니다. 혹시나 틀리거나 잘못된 부분에 대한 지적은 감사히 받겠습니다!