Dynamic Programming(동적 계획법)은 큰 문제를 작은 하위 문제들로 나누어 해결하는 알고리즘입니다. 이 알고리즘은 하위 문제들의 해결책을 저장하고 재사용하여 중복 계산을 피하며 효율적인 문제 해결을 가능하게 합니다.

Dynamic Programming은 다음과 같은 특징을 가지고 있습니다:

1. 최적 부분 구조(Optimal Substructure): 큰 문제의 최적 해결책은 작은 하위 문제의 최적 해결책으로부터 구성될 수 있습니다.
2. 중복 부분 문제(Overlapping Subproblems): 작은 하위 문제들을 해결하는 과정에서 동일한 하위 문제들이 반복적으로 발생합니다.

Dynamic Programming 알고리즘의 주요 단계는 다음과 같습니다:

1. 하위 문제 정의: 큰 문제를 해결하기 위해 작은 하위 문제들을 정의합니다. 이 단계에서 하위 문제의 입력과 출력을 명확하게 정의해야 합니다.
2. 하위 문제의 해결책 저장: 각 하위 문제의 해결책을 저장하기 위한 메모리 공간을 할당합니다. 이를 통해 중복 계산을 피하고 해결책을 재사용할 수 있습니다.
3. 재귀적인 접근 또는 반복적인 접근: 동일한 하위 문제들을 반복적으로 해결하거나, 재귀적으로 하위 문제를 해결하여 최종 문제의 해결책을 얻습니다.
4. 최종 문제의 해결책 반환: 하위 문제들의 해결책을 결합하여 최종 문제의 해결책을 반환합니다.

Dynamic Programming은 최적화 문제나 최단 경로 문제와 같이 여러 하위 문제로 나눌 수 있는 문제에 효과적으로 적용됩니다. 예를 들어, 피보나치 수열, 배낭 문제, 최장 증가 부분 수열 등이 Dynamic Programming을 활용하여 효율적으로 해결할 수 있는 대표적인 예시입니다.

Dynamic Programming에서는 두 가지 주요 기법인 "타뷸레이션(Tabulation)"과 "메모이제이션(Memoization)"을 사용할 수 있습니다. 이 두 가지 기법은 하위 문제의 해결책을 저장하고 재사용함으로써 중복 계산을 피하는 목적으로 사용됩니다.

타뷸레이션(Tabulation)은 보텀업(Bottom-up) 방식으로 동작하는 기법입니다. 작은 하위 문제부터 시작하여 상위 문제의 해결책까지 순차적으로 계산하여 저장합니다. 이렇게 하면 모든 하위 문제들을 한 번씩만 계산하면서 중복 계산을 피할 수 있습니다.

메모이제이션(Memoization)은 탑다운(Top-down) 방식으로 동작하는 기법입니다. 재귀적인 방식으로 하위 문제들을 해결하면서 해결책을 저장하고, 동일한 하위 문제를 다시 만나면 저장된 해결책을 바로 반환하여 중복 계산을 피합니다. 이를 위해 캐시(Cache) 또는 메모리 공간을 사용하여 하위 문제의 해결책을 저장합니다.

두 기법은 각각의 장단점이 있습니다. 타뷸레이션은 작은 하위 문제들을 반복적으로 해결하므로 계산 순서가 명확하고 성능이 일반적으로 더 좋을 수 있습니다. 반면에 메모이제이션은 필요한 하위 문제들만을 선택적으로 해결하므로 불필요한 계산을 줄일 수 있고, 재귀적인 방식으로 알고리즘을 표현하기에 직관적이고 간결한 코드를 작성할 수 있습니다.

Dynamic Programming에서는 타뷸레이션과 메모이제이션을 적절히 조합하여 사용할 수 있습니다. 타뷸레이션을 통해 하위 문제들의 해결책을 계산하고 저장한 뒤, 메모이제이션을 이용하여 중복 계산을 피하는 등의 최적화를 할 수 있습니다. 이를 통해 효율적이고 간결한 Dynamic Programming 알고리즘을 개발할 수 있습니다.

예시 코드