# 개요

동적 계획법(Dynamic Programming, DP)은 복잡한 문제를 해결하기 위해 문제를 더 작은 하위 문제로 나누고, 이 하위 문제의 결과를 재사용하여 전체 문제를 효율적으로 해결하는 방법론이다. 이는 일반적으로 최적화 문제에 적용되며, 주어진 문제의 최적 해를 구하기 위해 사용된다. 동적 계획법은 연산의 중복을 피함으로써 계산 효율성을 크게 향상시킬 수 있다.

#### 핵심 개념

**Overlapping Subproblems**

동적 계획법의 첫 번째 핵심 개념은 문제를 해결하는 과정에서 중복된 하위 문제가 반복해서 등장한다는 점이다. 예를 들어 피보나치 수열을 계산할 때, 여러 피보나치 수를 계산하는 과정에서 동일한 값이 여러 번 계산될 수 있다. DP에서는 이러한 중복 계산을 방지하기 위해 하위 문제의 결과를 메모이제이션(Memoization) 기법을 통해 저장하고 재사용한다.

**Optimal Substructure**

Optimal Substructure는 전체 문제의 최적 해가 그 하위 문제들의 최적 해로부터 구성될 수 있다는 것을 의미한다. 이 특성 덕분에, 동적 계획법은 하위 문제를 독립적으로 해결한 후, 이를 결합하여 전체 문제의 해를 도출할 수 있다.

**Bottom-Up Approach와 Top-Down Approach**

동적 계획법에서는 두 가지 주요 접근 방식이 있다.

* **Top-Down Approach:** 이 방법은 주어진 문제를 재귀적으로 더 작은 하위 문제로 분할한 후, 하위 문제를 해결하면서 그 결과를 저장하여 나중에 재사용하는 방식이다. 이는 메모이제이션과 함께 사용된다.
* **Bottom-Up Approach:** 이 방법은 가장 작은 하위 문제부터 시작하여 점진적으로 더 큰 문제를 해결해 나가는 방식이다. 이 방법에서는 보통 테이블을 사용하여 하위 문제의 결과를 저장하고, 최종적으로 주어진 문제의 해를 계산한다.

#### 동적 계획법의 요소

**상태 정의 (State Definition)**

동적 계획법에서는 먼저 문제를 해결하기 위한 상태(State)를 정의해야 한다. 상태는 문제의 특정 부분 문제를 나타내며, 이 상태를 기반으로 하위 문제를 정의하고 해결해 나간다. 예를 들어, LCS(Longest Common Subsequence) 문제에서는 두 문자열의 길이를 상태로 정의하여 최장 공통 부분 수열의 길이를 계산할 수 있다.

**상태 전이 (State Transition)**

상태가 정의되면, 상태 간의 전이 관계를 정의해야 한다. 상태 전이(State Transition)는 하나의 상태에서 다른 상태로 이동하는 규칙을 의미하며, 이 규칙에 따라 하위 문제의 해가 더 큰 문제의 해로 확장된다. 일반적으로 상태 전이는 점화식(Recurrence Relation)으로 표현된다.

**초기 조건 및 경계 조건 (Initial and Boundary Conditions)**

동적 계획법에서는 초기 상태와 경계 조건을 정의해야 한다. 초기 조건은 가장 작은 하위 문제의 해를 나타내며, 경계 조건은 문제의 범위를 설정하는 역할을 한다. 이러한 조건들이 명확하게 정의되어야 동적 계획법이 올바르게 작동할 수 있다.

#### 메모이제이션과 테이블링 (Memoization and Tabulation)

동적 계획법에서는 중복된 계산을 피하기 위해 결과를 저장하는 방법이 필수적이다. 이를 위해 메모이제이션과 테이블링 두 가지 방법이 사용된다.

* **메모이제이션 (Memoization):** 하위 문제의 결과를 계산할 때, 이미 계산된 결과를 메모리에 저장해 두고, 필요할 때 이를 재사용하는 기법이다. 주로 재귀적인 접근법에서 사용된다.
* **테이블링 (Tabulation):** 하위 문제의 결과를 테이블에 저장하여, 필요할 때 이를 참조하는 기법이다. 이는 주로 반복적인 접근법에서 사용되며, 하위 문제부터 시작하여 상위 문제를 해결해 나가는 Bottom-Up 방식에 주로 사용된다.

#### 동적 계획법의 한계와 문제점

동적 계획법은 매우 강력한 방법이지만, 모든 문제에 적합한 것은 아니다.

* **상태 공간의 크기:** 문제의 상태 공간이 지나치게 크면, 메모이제이션이나 테이블링에 필요한 메모리의 양이 비효율적일 수 있다.
* **정확한 상태 정의의 어려움:** 문제를 해결하기 위해 올바르고 효율적인 상태를 정의하는 것이 어려울 수 있다. 이는 DP 알고리즘을 설계할 때 큰 도전 과제가 될 수 있다.