동적 계획법(Dynamic Programming, DP)은 복잡한 문제를 효율적으로 해결하기 위한 알고리즘 설계 기법입니다. 이 방법은 문제를 더 작고 중복되는 하위 문제(Subproblem)로 분할하고, 각 하위 문제의 해답을 저장하여 동일한 하위 문제가 다시 계산되는 것을 방지함으로써 전체적인 처리 속도를 향상시킵니다. 주로 최적 부분 구조(Optimal Substructure)와 중복되는 하위 문제(Overlapping Subproblems)라는 두 가지 특성을 갖는 문제에 적용됩니다.
핵심 구성 요소
- 상태 정의 (Defining States): 문제의 특정 시점이나 부분 문제의 해를 나타내는 방법을 명확히 합니다. 이는 주로 하나 이상의 변수를 사용하여 표현됩니다.
- 상태 전이 방정식 (State Transition Equation): 현재 상태의 해를 이전 상태 또는 더 작은 하위 문제의 해를 기반으로 어떻게 도출할 수 있는지에 대한 관계식을 수립합니다. 이는 점화식의 형태로 나타납니다.
- 기저 조건 초기화 (Initializing Base Conditions): 가장 작고 간단한 하위 문제들의 해를 직접 계산하여 초기값으로 설정합니다. 이는 재귀 또는 반복 계산의 시작점이 됩니다.
동적 계획법의 필요성
동적 계획법은 다른 접근 방식에 비해 훨씬 효율적인 실행 시간을 제공하는 경우가 많습니다. 하위 문제들의 패턴과 관계를 정확히 파악할 수 있다면, 복잡한 문제도 유연하게 해결할 수 있는 강력한 도구입니다.
동적 계획법의 분류
동적 계획법은 해결하려는 문제의 구조에 따라 여러 가지 유형으로 분류될 수 있습니다. 이러한 분류는 엄격하게 독립적이지 않으며, 실제 문제에서는 여러 유형의 DP 기법이 복합적으로 사용될 수 있습니다.
- 선형 DP (Linear DP): 보통 1차원 또는 2차원 배열로 상태를 표현하며, 상태 전이가 선형적인 순서로 진행됩니다. 최장 증가 부분 수열(LIS), 0/1 배낭 문제, 완전 배낭 문제, 최대 부분 배열 합 등이 대표적인 예시입니다.
- 구간 DP (Interval DP): 주로 구간이나 부분 문제의 분할 및 병합을 다룹니다. 구간을 나누거나 합치는 방식으로 상태 전이가 이루어지며, 돌멩이 합치기(Stone Merging)와 같은 문제가 이 범주에 속합니다.
- 트리 DP (Tree DP): 트리 구조를 가진 문제에 적용됩니다. 상태 전이 방정식은 트리의 서브트리나 자식 노드를 기반으로 구성됩니다.
- 상태 압축 DP (State Compression DP): 상태 공간이 크지만 특정 패턴을 통해 압축할 수 있는 문제에 사용됩니다. 비트 연산이나 다른 압축 기법을 통해 상태를 효율적으로 표현합니다.
- 자릿수 DP (Digit DP): 숫자의 각 자릿수와 관련된 문제에 활용됩니다. 자릿수의 값을 기반으로 상태 전이가 정의됩니다.
- 확률 DP (Probability DP): 확률이나 기댓값과 관련된 문제에 적용됩니다. 상태 전이는 확률의 가중 합을 기반으로 계산됩니다.
- 다차원 DP (Multidimensional DP): 여러 차원의 상태 표현을 사용하는 동적 계획법입니다. 2차원 배낭 문제와 같이 여러 제약 조건을 동시에 고려해야 하는 경우에 사용됩니다.
DP 최적화 기법
동적 계획법의 효율성을 더욱 높이기 위해 상태 전이 방정식의 계산을 개선하거나 공간 복잡도를 최적화하는 다양한 기법들이 있습니다.
- 기울기 최적화 (Convex Hull Trick / Slope Optimization)
- 단조 큐 최적화 (Monotonic Queue Optimization)
- 슬라이딩 윈도우/롤링 배열 최적화 (Sliding Window / Rolling Array Optimization)
예제 문제: P1002 \[NOIP 2002\] 병사 건너뛰기
문제 설명
바둑판의 (0, 0) 지점에 위치한 병사(졸)가 목표 지점 (N, M)까지 이동해야 합니다. 병사는 아래쪽 또는 오른쪽으로만 이동할 수 있습니다. 바둑판의 특정 지점 (knight_X, knight_Y)에는 상대방의 말(Knight)이 있으며, 말의 현재 위치와 말이 한 번에 이동할 수 있는 모든 지점은 '말의 통제 지점'으로 간주됩니다. 병사는 이 통제 지점을 지날 수 없습니다.
말의 위치는 고정되어 있으며, 병사가 한 칸 이동할 때 말이 함께 움직이지는 않습니다. (0, 0)에서 (N, M)까지 병사가 이동할 수 있는 유효한 경로의 총 개수를 계산하시오.
입력 형식
한 줄에 네 개의 정수 N, M, knight_X, knight_Y가 공백으로 구분되어 주어집니다. 각각 목표 지점의 행/열 좌표와 말의 행/열 좌표를 나타냅니다.
출력 형식
병사가 목표 지점까지 도달할 수 있는 경로의 총 개수를 나타내는 정수 하나를 출력합니다.
입력 예시 #1
6 6 3 3
출력 예시 #1
6
제약 조건
모든 데이터에 대해 1 ≤ N, M ≤ 20, 0 ≤ knight_X, knight_Y ≤ 20.
문제 분석
병사가 아래쪽 또는 오른쪽으로만 이동할 수 있다는 제약 조건은 동적 계획법을 적용하기에 매우 적합합니다. 목표 지점 (N, M)까지 도달하는 경로의 수는, 바로 위 칸 (N-1, M)에서 오는 경로의 수와 바로 왼쪽 칸 (N, M-1)에서 오는 경로의 수를 합한 것과 같습니다.
핵심은 말의 통제 지점을 처리하는 것입니다. 말의 위치와 말이 이동할 수 있는 8개의 지점은 병사가 지나갈 수 없는 경로가 됩니다. 이 지점들을 미리 표시(차단)하여 DP 계산 시 해당 지점의 경로 수를 0으로 설정하면 됩니다. 편의를 위해 모든 좌표를 1씩 증가시켜 1-기반 인덱싱을 사용하고, 배열의 인덱스 0을 경계 조건으로 활용합니다.
C++ 코드 예시
#include <iostream>
#include <vector>
// 말의 8가지 이동 방향 (dr: row 변화량, dc: column 변화량)
int dr[] = {-2, -2, -1, -1, 1, 1, 2, 2};
int dc[] = {-1, 1, -2, 2, -2, 2, -1, 1};
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int targetRow, targetCol, knightInitialRow, knightInitialCol;
std::cin >> targetRow >> targetCol >> knightInitialRow >> knightInitialCol;
// 문제의 0-기반 좌표를 1-기반으로 변환하여 배열 인덱스 사용 편의성 증대
targetRow++;
targetCol++;
knightInitialRow++;
knightInitialCol++;
// 'blocked' 배열: 병사가 이동할 수 없는 지점(말의 통제 지점)을 표시
// 최대 N, M이 20이므로 25x25 크기로 충분 (1-기반 인덱싱 고려)
std::vector<std::vector<bool>> blocked(25, std::vector<bool>(25, false));
// 말의 현재 위치를 통제 지점으로 표시
blocked[knightInitialRow][knightInitialCol] = true;
// 말이 이동할 수 있는 8개 지점을 통제 지점으로 표시
for (int i = 0; i < 8; ++i) {
int nextRow = knightInitialRow + dr[i];
int nextCol = knightInitialCol + dc[i];
// 바둑판 경계 내에 있는 경우에만 표시
if (nextRow >= 1 && nextRow <= targetRow &&
nextCol >= 1 && nextCol <= targetCol) {
blocked[nextRow][nextCol] = true;
}
}
// 'pathCounts' 배열: 각 지점까지 도달하는 경로의 수를 저장
// 경로의 수가 매우 커질 수 있으므로 long long 사용
std::vector<std::vector<long long>> pathCounts(25, std::vector<long long>(25, 0));
// 시작 지점 (1, 1)의 경로 수 초기화
// 만약 시작 지점이 말의 통제 지점이라면 경로 수는 0
if (!blocked[1][1]) {
pathCounts[1][1] = 1;
}
// DP 테이블 채우기
for (int r = 1; r <= targetRow; ++r) {
for (int c = 1; c <= targetCol; ++c) {
// 현재 지점이 말의 통제 지점이거나 시작 지점인 경우 건너뛰기
if (blocked[r][c] || (r == 1 && c == 1)) {
continue;
}
// 현재 지점 (r, c)로 올 수 있는 경로는
// 위쪽 지점 (r-1, c)에서 오거나 왼쪽 지점 (r, c-1)에서 오는 경우의 합
// 배열의 0번 인덱스에 해당하는 값들은 0으로 초기화되어 있으므로,
// r=1일 때 pathCounts[0][c]는 0이 되고, c=1일 때 pathCounts[r][0]도 0이 된다.
pathCounts[r][c] = pathCounts[r - 1][c] + pathCounts[r][c - 1];
}
}
// 목표 지점 (targetRow, targetCol)까지의 총 경로 수 출력
std::cout << pathCounts[targetRow][targetCol] << std::endl;
return 0;
}