Dynamic Programming

동적 계획법, 다이나믹 프로그래밍(Dynamic Programming, DP) : 큰 문제를 작게 나누고, 같은 문제라면 한번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법이다.

최적의 해를 구하는 문제는 많은 연산 시간과 메모리가 필요해 컴퓨터로도 해결하기 어려운 문제이다. 이러한 문제들 중에서 특정 문제는 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 상승 시킬 수 있다. 기존의 알고리즘이 해결하지 못하는 문제들 중 다이나믹 프로그래밍 기법을 통해서 해결할 수 있는 문제가 있다. 대표적인 예시로 피보나치 수열이 있다.

DP 기법을 적용시키기 위한 조건

다이나믹 프로그래밍을 사용하기 위해서는 해당 하는 문제가 다음 2가지 조건을 만족해야 한다.

최적 부분 구조(Optimal Substructure): 큰 문제의 최적해가 작은 문제의 최적해로 이루어진 구조이다. ⇒ 이를 통해 점화식의 형태로 표현 가능함을 확인할 수 있다.

예를 들어, 피보나치 수열에서 F(n) = F(n-1) + F(n-2)와 같이 큰 문제를 작은 문제로 나눌 수 있고 이는 큰 문제에서도 동일하다.
중복되는 부분 문제(Overlapping Subproblems) : 동일한 부분 문제가 반복되는 경우이다. ⇒ 다이나믹 프로그래밍의 메모제이션 혹은 DP 테이블을 통해서 작은 문제의 답을 저장 및 재사용을 통해서 문제 해결의 효율성을 높일 수 있다.

예를 들어, 피보나치 수열을 재귀적으로 해결하는 과정에서 동일한 부분 문제가 반복적으로 호출되는 것을 예로 들 수 있다.

DP 문제 해결의 두가지 방식

탑다운(Top-Down) 접근 - 메모이제이션(Memoization):
- 재귀적 접근 방식으로, 함수 호출 시 결과를 저장하여 중복 계산을 피합니다.
- 재귀 함수를 사용하면 함수를 다시 호출 했을 때 메모리 상에 적재되는 일련의 과정을 따라야 하므로 오버헤드(알고리즘 외에 연산을 위해 필요한 시간)가 발생 한다. 따라서, 재귀 함수 보다는 반복문을 사용하는 것이 성능이 좋다.
- 이처럼 재귀 함수를 이용하여 다이나믹 프로그래밍 소스코드를 작성하는 방법을, 큰 문제를 해결하기 위해서 작은 문제를 호출 한다고 하여 Top_Down방식 이라고 한다.
바텀업(Bottom-Up) 접근 - 타뷸레이션(Tabulation):
- 반복문을 사용하는 방식으로, 점화식을 정의하고 반복문을 통해서 작은 값부터 구하고자 하는 값까지 차근차근 답을 도출 한다고 하여 Bottom-Up 방식이라고 한다.
- 다이나믹 프로그래밍의 전형적인 형태는 바텀업 방식이다. 바텀업 방식에서 사용되는 결과 저장용 리스트는 ‘DP 테이블’ 이라고 부르며, 메모이 제이션은 탑다운 방식에 국한되어 사용되는 표현이다.
- 다이나믹 프로그래밍과 메모이제이션의 개념을 혼용해서 사용하는 경우도 있는데, 엄밀히 말하면 메모이제이션은 이전에 계산된 결과를 일시적으로 기록해 놓는 넓은 개념을 의미하므로, 다이나믹 프로그래밍과는 별도의 개념이다.

점화식

다이나믹 프로그래밍 기법을 사용하기 위해서는 결국, 최적 부분 구조와 중복되는 부분 문제를 만족해야 한다. 이는 결국 점화식을 만들기전 성립해야 두 조건과 같다. 즉, 점화식을 세우기 위해서는 최적 부분 구조와 중복되는 부분 문제를을 만족해야 한다.
탑다운, 바텀업 모두 점화식을 알아야지만 사용할 수 있는 방식이기에 다이나믹 프로그래밍 문제라는 걸 파악 한다면 점화식을 찾아야 하며, 다이나믹 프로그래밍 문제를 잘 풀기 위해서는 결국 점화식을 세우는 훈련이 되어 있어야 한다.

<나동빈, "이것이 코딩 테스트다", 216쪽>

문제를 푸는 첫 번째 단계는 (당연하게 들리겠지만) 주어진 문제가 다이나믹 프로그래밍 유형임을 파악하는 것이다. 특정한 문제를 완전 탐색 알고리즘으로 접근했을 때 시간이 매우 오래 걸리면 다이나믹 프로그래밍을 적용할 수 있는지 해결하고자 하는 부분 문제들의 중복 여불르 확인해보자.

일단 단순히 재귀 함수로 비효율적인 프로그램을 작성한 뒤에 (탑다운) 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면, 즉 메모제이션을 적용할 수 있으면 코드를 개선하는 방법도 좋은 아이디어이다. 앞서 다루었던 피보나치 수열의 에제 처럼 재귀 함수를 작성한 뒤에 나중에 메모이제이션 기법을 적용해 소스코드를 수정하는 것도 좋은 방법이다.

또한 가능하다면 재귀 함수를 이용하는 탑다운 방식 보다는 바텀업 방식으로 구현하는 것을 권장한다. 시스템상 재귀 함수의 스택 크기가 한정되어 있을 수 있기 때문이다. 실제로 앞에서 제시한 재귀 적인 피보나치 수열의 소스코드에서 오천 번째 이상의 큰 피보나치 수를 구하도록 하면 recursion depth와 관련된 오류가 발생한다.