7. 동적계획법(DP: Dynamic Programming)의 기초

동적계획법은 어떤 문제에서 최적해를 구해야할 때, 문제를 더이상 쪼갤 수 없는 단위로 쪼개서 제일 작은 부분부터 최적해를 누적해 나가는 방식으로 문제를 푸는 알고리즘을 의미합니다. 동적계획법이 가능한 것은 문제를 동일 형식의 연산이 반복될 수 있는 더 작은 문제로 쪼갤 수 있고, 작은 문제의 최적해를 이용해서 그보다 조금 더 큰 문제의 최적해를 도출할 수 있다는 것이 보장되기 때문입니다. 이러한 동적계획법의 풀이 방식에 근거하여 동적계획법 풀이는 크게 두가지가 핵심적으로 작동한다고 할 수 있는데 한 가지는 초기조건, 다른 한 가지는 점화식입니다.

초기조건은 말그대로 문제를 가장 작은 단위로 쪼개었을 때 연산없이 확정되어있는 최적해를 의미합니다. 동적계획법은 동일 연산을 가장 작은 크기의 문제부터 반복 적용하여 마지막으로 전체 문제의 답을 구하는 방식인데 문제는 그렇게 작게 더 작게 쪼개더라도 결국에는 더이상 쪼갤 수 없는 시작점이 존재하게 되어있습니다. 보통 연산을 적용할 수 없는 가장 작은 부분은 우리가 추정해서 도출하기보다 문제에서 주어지는 경우가 많으므로 저는 이 부분을 초기조건이라고 부릅니다. 초기 조건은 문제에서 친절하게 명시적으로 주어지는 경우도 있지만, 우리가 문제를 통해서 추정해야하는 경우도 많습니다. 문제를 잘 읽고 연산을 적용할 수 있는 가장 작은 단위가 무엇인지 그 시작점을 잘 찾는 것이 최종적인 답을 구하는 첫단추가 됩니다.

다음으로 점화식이 있습니다. 점화식은 앞에서 말한 연산에 해당합니다. 부분 문제의 계산을 통해 전체 문제의 답을 구할수 있도록 구현하는 것이 점화식을 구하는 방법입니다. 점화식은 그렇기 때문에 부분 계산의 결과값이 그 부분을 포함하는 더 큰 문제의 답을 도출하도록 구성되어 있습니다.

동적계획법을 설명할 때 가장 많이 예시로 드는 피보나치 수(Fibonacci Number)를 이용하여 다시 한번 이해해보도록 하겠습니다.

피보나치 수의 정의는 0과 1로 시작하며, 다음 피보나치 수는 바로 앞의 두 피보나치 수의 합이 된다고 되어있습니다.

피보나치 수: 위키백과

https://ko.wikipedia.org/wiki/%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98_%EC%88%98

정의를 보면 피보나치 수가 동적계획법을 설명하기에 아주 적절한 예시라는 것을 알 수 있습니다. 0과 1로 시작하며 라고 되어 있는 앞 부분은 바로 동적계획법의 초기 조건을 의미합니다. 또한 다음 피보나치 수는 바로 앞의 두 피보나치 수의 합 이라는 부분은 바로 점화식을 의미합니다. 즉 피보나치 수는 초기 조건으로 최초 두 개 항의 숫자가 0과 1, 연산으로는 앞 두 피보나치 수의 합이라는 부분문제의 형태로 구성되어 있는 동적계획법 문제인 것입니다.

그렇다면  python으로 피보나치 수 문제를 직접 풀어보면서 설명해보도록 하겠습니다.

2747번: 피보나치 수 - Baekjoon Online Judge

https://www.acmicpc.net/problem/2747

n = int(input())
 
## 초기조건으로 0과 1을 입력합니다.
fibonacci = []
fibonacci.append(0)
fibonacci.append(1)
 
## 피보나치 수를 만들기 위해서 앞의 두개의 값을 이용합니다.
## 3번째, 4번째, ..., n-1번째 피보나치 수를 만드는 문제를 풀다보면 n번째 피보나치수를 구할 수 있습니다. 
for i in range(2, int(n) + 1):
    fibonacci.append(fibonacci[i-1] + fibonacci[i-2])
 
## 가장 마지막에 있는 피보나치 수를 구하면 그 값이 n번째 피보나치 수가 됩니다.
print(fibonacci[-1])