동적계획법(Dynamic Programming, DP)
동적 계획법은 알고리즘 설계 기법의 하나로서 동적계획법 풀이는 단순하게 말하면 점화식의 연속입니다. 그리고 이런 점화식을 진행하는 방식에 따라 풀이를 다음과 같이 나눌 수 있습니다.
- 탑다운:(Top-Down): 최종 상태를 구하기 위해 아래 상태를 재귀적으로 구하는 방법
- 바텀업(Bottom-Up): 가장 작은 상태에서부터 쌓아나가는 방법
보통 Python의 재귀 속도 문제로 Python에서는 Bottom-Up 방식으로 코드를 짜는 것을 추천합니다.
DP와 분할정복의 특징
이 두 개념은 “”큰 문제를 작은 문제로 나눠서 푼다.”라는 공통점을 갖고 있습니다. 다만 분할 정복은 동적계획법과 달리 계산한 부분문제를 한번만 쓰고 더 이상 쓰지 않기 때문에 메모이제이션이 필요하지 않습니다. 분할 정복과 동적 계획법의 근본적인 차이입니다.
메모이제이션(menoization)
동적계획법 알고리즘의 대표적인 예 중 하나는 이항 계수의 계산입니다.
bino(a, b) = bino(a - 1, b) + bino(a -1, b -1)이라고 정의해보겠습니다. bino(4, 2)를 호출했을때 아래와 같이 함수가 재귀적으로 호출됩니다.
(a)에서느 bino(2, 1)는 bino(3, 1)rㅘ bino(3, 2)에서 모두 호출됩니다. bino(2,1 )은 bino(1, 0), bino(1, 1)을 재귀 호출하여 이 경우도 두번씩 호출됩니다. 동적계획법에는 이처럼 중복된 계산을 막기 위해 저장된 결과를 배열에 저장한 뒤, 다음 계산이 필요할 때는 저장된 값을 불러와서 중복을 없애면 (b)처럼 함수 호출이 줄어들게끔 사용할 수 있습니다. 따라서, 시간 복잡도도 줄어듭니다. 이러한 기법을 메모이제이션이라고 합니다.
code
백준 알고리즘의 피보나치 수(링크를 타고 들어가서 확인해주시면 감사하겠습니다.)
Bottom-up
Top-down
참조: 블로그, 수니비움님의 강의자료