동적 프로그래밍(Dynamic Programming) 이란?

동적 프로그래밍은 복잡한 문제를 여러 개의 단순한 하위 문제로 나누어 해결하는 알고리즘 설계 기법이다.

이 기법은 특히 다음 두 가지 특징을 가진 문제에 매우 효과적이다.

1. 겹치는 문제(Overlapping Subproblems)

큰 문제를 해결하는 과정에서 동일한 하위 문제를 반복적으로 계산해야 할 때.

예를 들어, 피보나치 수를 계산할 때 fib(5)를 구하려면 fib(4)와 fib(3)을, fib(4)를 구하려면 fib(3)과 fib(2)를 계산한다.

여기서 fib(3)이 2번 계산된다.

DP는 이렇게 반복되는 계산 결과를 저장해 두었다가 필요할 때 재사용함으로써 효율성을 높인다.

2. 최적 부분 구조(Optimal Substructure)

전체 문제의 최적 해가 하위 문제의 최적 해들로 구성되어 있을 때.

즉, 큰 문제의 최적 해가 작은 문제들의 최적 해를 합쳐서 만들 수 있다는 의미다.

DP 문제 해결의 두 가지 접근 방식

메모이제이션(Memoization) / 하향식(Top-down)