Dynamic Programming이란?

[junjange]

Dynamic Programming, 또는 DP는 문제를 작은 하위 문제로 나누어 각각의 해를 저장하고 재사용하면서 전체 문제를 효율적으로 해결하는 기법입니다.

예를 들어 피보나치 수열 계산에서 각 수를 구할 때 앞에서 계산한 결과를 저장하고 재사용함으로써, 중복 계산을 피하고 시간 복잡도를 획기적으로 줄일 수 있습니다. DP는 크게 두 가지 접근 방식으로 나뉩니다. 하나는 '탑다운' 방식으로 재귀와 메모이제이션을 통해 해결하는 것이고, 다른 하나는 '바텀업' 방식으로 테이블을 채워나가며 문제를 해결하는 방식입니다.

실제로 저는 DP를 활용해 최단 경로, 배낭 문제와 같은 최적화 문제를 해결한 경험이 있습니다. 문제를 더 작게 나누어 접근하니 효율적으로 풀이할 수 있었으며, 계산 속도도 크게 향상되었습니다.