다이나믹 프로그래밍(Dynamic Programming, 동적계획법)이란 뭘까요?
큰 문제를 작은 문제로 나누어서 푸는 방법을 다이나믹 프로그래밍이라고 합니다.
이름의 '다이나믹'과는 거리가 먼 방식입니다. 실제로 다이나믹 프로그래밍의 고안자 벨만은 dynamic이라는 단어를 그냥 멋있어서 선택했다고 합니다.
문제가 두 가지 속성을 만족해야 다이나믹 프로그래밍을 사용해 문제를 풀 수 있습니다.
- Overlapping Subproblem (겹치는 부분문제)
: 큰 문제를 작은 문제로 쪼갤 수 있을 때, 동일한 작은 문제 겹치는 경우. - Optimal Substructure (최적부분구조)
: 문제의 정답을 작은 문제의 정답을 합하는 것으로 구할 수 있을 때
다이나믹 프로그래밍으로 풀 수 있는 대표적인 문제로는 피보나치 수, 이항계수 등이 있습니다.
최적부분구조를 만족하기 때문에 정답을 한 번 구한 것을 저장해서 그 정답이 필요할 때마다 다시 계산하지 않고 메모해둔 것을 불러서 쓰면 되겠죠. 이것을 메모이제이션(Memoization)이라고 합니다.
메모이제이션을 적용할 수 있으려면 함수의 반환값이 그 입력값으로만 결정돼야 합니다. 이때 이 함수를 참조적 투명 함수(referential transparent function)라고 합니다.
구현 방식은 두가지 방법이 있습니다.
- Top-down
- Bottom-up
Top-down 방식은 재귀호출을 이용해 풀 수 있고, Bottom-up 방식은 반복문으로 풀 수 있습니다.
Bottom-up 방식은 해를 구하기 이전까지 모든 해를 구해야 하기 때문에 Top-down 방식보다 느릴 수도 있습니다. 하지만 Top-down 방식은 함수 호출스택을 이용하기 때문에 그 부분을 감안하면 일반적인 경우(모든 해를 구해야 하는 경우) 두 방식은 비슷하다고 볼 수 있을 것 같습니다.
반응형
