# 동적 계획법 문제 풀이 방법

앞의 두 절에서는 동적 계획법 문제의 주요 특성을 살펴보았다. 이제 더 실용적인 두 질문을 알아보자.

1. 어떤 문제가 동적 계획법 문제인지 어떻게 판단할까?
2. 동적 계획법 문제는 어디서 시작하며, 전체 풀이 단계는 어떻게 될까?

## 문제 판단

대체로 중복 부분 문제와 최적 부분 구조가 있고 무후효성을 만족하면 동적 계획법에 적합하다. 하지만 문제 설명에서 이러한 특성을 바로 끌어내기는 어렵다. 따라서 보통 조건을 완화하여 **먼저 백트래킹(모든 경우 열거)으로 풀기에 적합한지 살펴본다**.

**백트래킹에 적합한 문제는 보통 '의사 결정 트리 모형'을 따른다**. 각 노드가 결정 하나를, 각 경로가 결정의 순서를 나타내는 트리 구조로 표현할 수 있는 문제다.

즉, 명확한 결정 개념이 있고 연속된 결정을 통해 해가 만들어진다면 의사 결정 트리 모형을 만족하며, 보통 백트래킹으로 해결할 수 있다.

여기에 더해 동적 계획법 문제로 판단할 때 '가산점'이 되는 요소도 있다.

- 최댓값, 최솟값, 가장 많은 수, 가장 적은 수 등의 최적화 표현이 포함되어 있다.
- 상태를 리스트, 다차원 행렬, 트리로 표현할 수 있고, 한 상태와 주변 상태들 사이에 점화 관계가 있다.

반대로 '감점' 요소도 있다.

- 최적해 하나가 아니라 가능한 모든 해결 방법을 찾는 것이 목표다.
- 문제 설명에 순열이나 조합의 특성이 뚜렷하며, 구체적인 여러 방법을 반환해야 한다.

의사 결정 트리 모형을 만족하면서 '가산점' 요소가 뚜렷하다면, 우선 동적 계획법 문제라고 가정하고 풀이 과정에서 확인해 볼 수 있다.

## 문제 해결 단계

동적 계획법의 풀이 흐름은 문제의 성격과 난이도에 따라 다르지만, 보통 결정 설명, 상태 정의, $dp$ 테이블 구성, 상태 전이 식 도출, 경계 조건 결정 등의 단계를 따른다.

단계를 더 구체적으로 보여 주기 위해 대표적인 '최소 경로 합' 문제를 예로 든다.

!!! question "문제"

    $n \times m$의 2차원 격자 `grid`가 주어진다. 각 칸에는 그 칸의 비용인 음이 아닌 정수가 들어 있다. 로봇은 왼쪽 위에서 출발하여 매번 아래 또는 오른쪽으로 한 칸씩만 이동하고, 오른쪽 아래에 도착한다. 왼쪽 위에서 오른쪽 아래까지의 최소 경로 합을 반환하라.

아래 그림의 격자에서는 최소 경로 합이 $13$이다.

![최소 경로 합 예시 데이터](dp_solution_pipeline.assets/min_path_sum_example.png)

**1단계: 매 차례의 결정을 생각하고 상태를 정의하여 $dp$ 테이블을 얻는다**

이 문제에서 매 차례의 결정은 현재 칸에서 아래 또는 오른쪽으로 한 칸 이동하는 것이다. 현재 칸의 행과 열 인덱스가 $[i, j]$라면 이동 후에는 $[i+1, j]$ 또는 $[i, j+1]$이 된다. 따라서 상태는 행 인덱스와 열 인덱스라는 두 변수를 포함해야 하며 $[i, j]$로 표시한다.

상태 $[i, j]$의 부분 문제는 출발점 $[0, 0]$에서 $[i, j]$까지의 최소 경로 합이고, 해를 $dp[i, j]$라고 한다.

이로써 아래 그림처럼 입력 격자 $grid$와 크기가 같은 2차원 $dp$ 행렬을 얻는다.

![상태 정의와 dp 테이블](dp_solution_pipeline.assets/min_path_sum_solution_state_definition.png)

!!! note "참고"

    동적 계획법과 백트래킹 과정은 결정의 순서로 표현할 수 있으며, 상태는 모든 결정 변수로 이루어진다. 상태에는 풀이의 진행 정도를 나타내는 모든 변수가 포함되어야 한다. 즉, 다음 상태를 도출하기에 충분한 정보가 있어야 한다.
    
    각 상태는 부분 문제 하나에 대응하며, 모든 부분 문제의 해를 저장하기 위해 $dp$ 테이블을 정의한다. 상태의 독립 변수 각각이 $dp$ 테이블의 한 차원이 된다. 본질적으로 $dp$ 테이블은 상태와 부분 문제의 해 사이의 매핑이다.

**2단계: 최적 부분 구조를 찾아 상태 전이 식을 도출한다**

상태 $[i, j]$는 위쪽 칸 $[i-1, j]$ 또는 왼쪽 칸 $[i, j-1]$에서만 올 수 있다. 따라서 최적 부분 구조는 다음과 같다. $[i, j]$까지의 최소 경로 합은 $[i, j-1]$까지의 최소 경로 합과 $[i-1, j]$까지의 최소 경로 합 중 작은 쪽에 의해 결정된다.

위 분석으로 아래 그림의 상태 전이 식을 얻는다.

$$
dp[i, j] = \min(dp[i-1, j], dp[i, j-1]) + grid[i, j]
$$

![최적 부분 구조와 상태 전이 식](dp_solution_pipeline.assets/min_path_sum_solution_state_transition.png)

!!! note "참고"

    정의한 $dp$ 테이블을 바탕으로 원래 문제와 부분 문제의 관계를 생각하고, 부분 문제의 최적해로 원래 문제의 최적해를 만드는 방법, 즉 최적 부분 구조를 찾는다.

    최적 부분 구조를 찾으면 이를 이용해 상태 전이 식을 세울 수 있다.

**3단계: 경계 조건과 상태 전이 순서를 정한다**

이 문제에서 첫 행의 상태는 왼쪽 상태에서만, 첫 열의 상태는 위쪽 상태에서만 올 수 있다. 따라서 첫 행 $i = 0$과 첫 열 $j = 0$이 경계 조건이다.

아래 그림과 같이 각 칸은 왼쪽 칸과 위쪽 칸에서 전이되므로, 바깥 반복문은 행을, 안쪽 반복문은 열을 순회한다.

![경계 조건과 상태 전이 순서](dp_solution_pipeline.assets/min_path_sum_solution_initial_state.png)

!!! note "참고"

    경계 조건은 동적 계획법에서 $dp$ 테이블을 초기화하는 데, 탐색에서는 가지치기에 사용한다.
    
    상태 전이 순서의 핵심은 현재 문제의 해를 계산하기 전에 그 해가 의존하는 모든 작은 부분 문제의 해가 올바르게 계산되어 있도록 하는 것이다.

이제 동적 계획법 코드를 바로 작성할 수 있다. 하지만 부분 문제로 나누는 사고는 위에서 아래로 진행하므로, '완전 탐색 $\rightarrow$ 메모이제이션을 이용한 탐색 $\rightarrow$ 동적 계획법' 순서로 구현하는 편이 사고 흐름에 더 자연스럽다.

### 방법 1: 완전 탐색

상태 $[i, j]$에서 탐색을 시작하여 더 작은 상태 $[i-1, j]$와 $[i, j-1]$로 계속 나눈다. 재귀 함수에는 다음 요소가 포함된다.

- **재귀 매개변수**: 상태 $[i, j]$.
- **반환값**: $[0, 0]$에서 $[i, j]$까지의 최소 경로 합 $dp[i, j]$.
- **종료 조건**: $i = 0$이고 $j = 0$이면 비용 $grid[0, 0]$을 반환한다.
- **가지치기**: $i < 0$ 또는 $j < 0$이면 인덱스가 범위를 벗어나므로 불가능함을 나타내는 비용 $+\infty$를 반환한다.

구현 코드는 다음과 같다.

```src
[file]{min_path_sum}-[class]{}-[func]{min_path_sum_dfs}
```

아래 그림은 $dp[2, 1]$을 루트로 하는 재귀 트리다. 중복 부분 문제가 포함되어 있으며, 그 수는 격자 `grid`의 크기가 커질수록 급격히 늘어난다.

중복 부분 문제가 생기는 근본적인 이유는 **왼쪽 위에서 어떤 칸에 도달하는 경로가 여러 개 있기 때문**이다.

![완전 탐색의 재귀 트리](dp_solution_pipeline.assets/min_path_sum_dfs.png)

각 상태에는 아래와 오른쪽이라는 두 선택이 있고, 왼쪽 위에서 오른쪽 아래까지는 총 $m + n - 2$ 번 이동해야 한다. 따라서 최악의 시간 복잡도는 $O(2^{m + n})$이며, $n$과 $m$은 각각 격자의 행 수와 열 수다. 이 계산은 경계 근처의 상황을 고려하지 않았다. 격자 경계에서는 선택이 하나뿐이므로 실제 경로 수는 이보다 적다.

### 방법 2: 메모이제이션을 이용한 탐색

격자 `grid`와 같은 크기의 메모이제이션 리스트 `mem`을 도입하여 각 부분 문제의 해를 기록하고 중복 부분 문제를 가지치기한다.

```src
[file]{min_path_sum}-[class]{}-[func]{min_path_sum_dfs_mem}
```

아래 그림과 같이 메모이제이션을 도입하면 모든 부분 문제의 해를 한 번만 계산한다. 따라서 시간 복잡도는 전체 상태 수, 즉 격자 크기인 $O(nm)$에 의해 결정된다.

![메모이제이션을 이용한 탐색의 재귀 트리](dp_solution_pipeline.assets/min_path_sum_dfs_mem.png)

### 방법 3: 동적 계획법

반복을 이용한 동적 계획법 구현은 다음과 같다.

```src
[file]{min_path_sum}-[class]{}-[func]{min_path_sum_dp}
```

아래 그림의 최소 경로 합 상태 전이 과정에서는 전체 격자를 순회하므로 **시간 복잡도는 $O(nm)$이다**.

배열 `dp`의 크기는 $n \times m$이므로 **공간 복잡도는 $O(nm)$이다**.

=== "<1>"
    ![최소 경로 합의 동적 계획법 과정](dp_solution_pipeline.assets/min_path_sum_dp_step1.png)

=== "<2>"
    ![최소 경로 합 동적 계획법 2단계](dp_solution_pipeline.assets/min_path_sum_dp_step2.png)

=== "<3>"
    ![최소 경로 합 동적 계획법 3단계](dp_solution_pipeline.assets/min_path_sum_dp_step3.png)

=== "<4>"
    ![최소 경로 합 동적 계획법 4단계](dp_solution_pipeline.assets/min_path_sum_dp_step4.png)

=== "<5>"
    ![최소 경로 합 동적 계획법 5단계](dp_solution_pipeline.assets/min_path_sum_dp_step5.png)

=== "<6>"
    ![최소 경로 합 동적 계획법 6단계](dp_solution_pipeline.assets/min_path_sum_dp_step6.png)

=== "<7>"
    ![최소 경로 합 동적 계획법 7단계](dp_solution_pipeline.assets/min_path_sum_dp_step7.png)

=== "<8>"
    ![최소 경로 합 동적 계획법 8단계](dp_solution_pipeline.assets/min_path_sum_dp_step8.png)

=== "<9>"
    ![최소 경로 합 동적 계획법 9단계](dp_solution_pipeline.assets/min_path_sum_dp_step9.png)

=== "<10>"
    ![최소 경로 합 동적 계획법 10단계](dp_solution_pipeline.assets/min_path_sum_dp_step10.png)

=== "<11>"
    ![최소 경로 합 동적 계획법 11단계](dp_solution_pipeline.assets/min_path_sum_dp_step11.png)

=== "<12>"
    ![최소 경로 합 동적 계획법 12단계](dp_solution_pipeline.assets/min_path_sum_dp_step12.png)

### 공간 최적화

각 칸은 왼쪽 칸과 위쪽 칸에만 의존하므로 한 행짜리 배열만으로 $dp$ 테이블을 구현할 수 있다.

배열 `dp`가 한 행의 상태만 나타내므로 첫 열의 상태를 미리 초기화할 수는 없다. 대신 각 행을 순회할 때 갱신해야 한다.

```src
[file]{min_path_sum}-[class]{}-[func]{min_path_sum_dp_comp}
```