1. Dynamic Programming(동적 계획법)이란?
복잡한 문제를 여러 개의 간단한 문제로 분리하여 부분의 문제들을 해결함으로써 최종적으로 복잡한 문제의 답을 구하는 방법
이 정의만 봤을 때는, 앞서 다뤘던 분할 정복(divide and conquer)와 매우 유사하다고 느낄 수 있다. 두 알고리즘 모두 큰 문제를 작은 문제로 나누어 해결한다는 점과 재귀를 활용한다는 점에서 그렇다. 하지만, 하위 문제의 중복성과 결과 저장 방식에서 명백한 차이가 존재한다.
원리와 구현 방식
- 큰 문제를 작은 문제로 나눌 수 있어야 한다
- 작은 문제들이 반복돼 나타나고, 이 작은 문제들의 결과값은 항상 같아야 한다
- 모든 작은 문제들을 한 번만 계산해 DP table에 저장하며, 추후 재사용할 때는 이 DP table을 이용한다. 이를 memoization 기법이라고 한다.
- top down 방식 & bottom-up 방식으로 구현할 수 있다.
피보나치 수열
DP의 대표적인 예시로 피보나치 수열을 들 수 있다. 피보나치 수열의 공식은 다음과 같다. D[N] = D[N-1] + D[N-2]
이 수열이 DP에 해당하는지 확인하기 위해서는, 큰 문제를 작은 문제로 나눌 수 있는지, 작은 문제가 계속 중복이 되는지를 확인할 수 있어야 한다. 피보나치 수열은 큰 문제를 작은 문제로 나누어 해결하는 문제이고, 계속 같은 문제가 중복되어 나타나므로, DP의 가장 대표적인 예시라고 할 수 있다. 추가적으로, 점화식을 세우기 위해서는 전체 문제와 부분 문제간의 인과 관계를 파악할 수 있어야 한다.
memoization 원리
memoization이란, 컴퓨터 프로그램을 실행할 때 이전에 계산한 값을 메모리에 저장해서 매번 다시 계산하지 않도록 하여 전체적인 실행속도를 빠르게 하는 기술을 의미한다.
위의 그림과 같이, 피보나치 수열에서는 중복 문제가 등장한다. 그렇기에 이런 작은 문제들을 DP table에 저장해 놓고, 나중에 같은 문제가 나왔을 때 DP table의 값을 이용하면 된다. 즉, 시간 복잡도 측면에서 많은 이득을 취할 수 있다.
top-down 방식
말 그대로 위에서부터 문제를 파악해 내려오는 방식으로, 주로 재귀함수 형태로 코드를 구현한다. 코드의 가독성이 좋고, 이해하기가 편리하다는 장점이 있다.
bottom-up 방식
가장 작은 부분 문제로부터 문제를 해결해가면서 점점 큰 문제로 확장해 나가는 방식이다. 주로 반복문의 형태로 구현된다.
위의 코드를 보면, for문을 2부터 돌리면서 2부터 점점 커지면서 값을 구해나가는 형태임을 확인할 수 있다.
