9184번 문제로 배운 DP의 의미
/ 8분 분량 / 문제 풀이
재귀 문제를 동적 프로그래밍으로 변환하는 과정을 거쳤습니다. 상태 공간 위의 값 전파 방식이라는 DP 사고방식을 경험했습니다.
재귀 문제를 동적 프로그래밍으로 변환하는 과정을 거쳤습니다. 상태 공간 위의 값 전파 방식이라는 DP 사고방식을 경험했습니다.
학습 주제
9184번 문제의 DP 개념 정복
백준의 대표 DP 입문 문제인 9184번을 통해 동적 프로그래밍의 의미를 탐구했습니다. "함수 호출을 배열 접근으로 바꾸는 것"이 아닌, 재귀 구조를 3차원 상태 공간의 문제로 접근해보았습니다.
질문과 탐구
- 재귀 함수 w(a,b,c)가 3차원 공간에서 수학적으로 어떤 의미인가?
- 이 함수의 의존 구조는 왜 DAG(순환 없는 방향 그래프)인가?
- 재귀식을 어떻게 DP 구조로 안전하게 변환할 수 있는가?
- 위상 정렬이 단순한 이론이 아니라 구체적으로 무엇인가?
핵심 학습 내용
1. w(a,b,c)는 3차원 필드 함수
처음에는 재귀 함수로 보였지만, 수학적으로 해석하면:
- 정의역: 정수 3차원 공간 (a,b,c)
- 치역: 정수 값
- 경계 조건: a≤0 또는 b≤0 또는 c≤0일 때 값이 1로 고정
- 천장: a>20 또는 b>20 또는 c>20일 때 w(20,20,20)으로 포화
2. 의존 그래프가 DAG인 이유
재귀식을 분석하면:
w(a,b,c) = w(a-1,b,c) + w(a-1,b-1,c) + ... (항상 a,b,c 중 하나라도 감소)
모든 재귀 호출은 좌표 합 (a+b+c)를 감소시킵니다. 따라서:
- 순환 경로가 불가능 (정수는 계속 줄어드는데 다시 같은 값이 될 수 없음)
- 의존 그래프는 100% DAG
- 위상 정렬이 존재하고, 위상 정렬 순서로 계산 가능
3. 재귀 → DP 변환의 정확한 의미
| 구분 | 재귀 | DP |
|---|---|---|
| 사고 | "이 값이 필요하면?" | "이 공간 전체를 생성하면?" |
| 접근 | 깊이 우선 (필요 시 계산) | 위상 정렬 (미리 전부 계산) |
| 스택 | 호출 스택 (깊이 제한) | 배열 (메모리 사용) |
| 중복 | 같은 상태 반복 계산 | 각 상태 한 번만 계산 |
4. 3중 for문이 위상 정렬인 이유
for (int a = 1; a <= 20; ++a) {
for (int b = 1; b <= 20; ++b) {
for (int c = 1; c <= 20; ++c) {
// dp[a][b][c] = 이전 상태들의 선형 결합
}
}
}
이 순서가 위상 정렬인 이유:
- dp[a][b][c]는 항상 a-1, b-1, c-1 쪽만 참조
- 3중 for문은 이 의존성을 자동으로 만족
- 처리 순서가 의존 관계를 어기지 않음
이해한 내용
이전 몰랐던 것
DP를 단순히 "중복 계산을 피하는 최적화"로 생각했습니다. 캐싱(memoization) 정도로만 이해했습니다.
새로 알게 된 것
DP는 다른 사고방식입니다:
- 상태 공간 구성: 답을 찾는 게 아니라 상태 공간 전체를 체계적으로 구성
- 위상 정렬: 의존성을 존중하는 순서가 자동으로 DP 알고리즘이 됨
- DAG 구조: "모든 참조가 감소 방향"이면 자동으로 DAG = 자동으로 DP 가능
- 물리적 해석: 3차원 배열은 단순 데이터 구조가 아니라 수학적 함수의 이산 샘플링
개념 정리
DP가 작동하는 조건:
- 큰 문제가 작은 문제의 조합으로 분해 가능
- 작은 문제가 반복됨
- 의존성이 순환 없음 (DAG)
9184는 이 3가지를 만족하는 예제입니다.
구현 코드 (C++)
#include <bits/stdc++.h>
using namespace std;\n
int dp[21][21][21];
int main() {
// Base case: 0층을 1로 초기화
for (int a = 0; a <= 20; ++a)
for (int b = 0; b <= 20; ++b)
for (int c = 0; c <= 20; ++c)
if (a == 0 || b == 0 || c == 0)
dp[a][b][c] = 1;
// DP 테이블 채우기 (위상 정렬 순서)
for (int a = 1; a <= 20; ++a) {
for (int b = 1; b <= 20; ++b) {
for (int c = 1; c <= 20; ++c) {
if (a < b && b < c) {
dp[a][b][c] = dp[a][b][c-1]
+ dp[a][b-1][c-1]
- dp[a][b-1][c];
} else {
dp[a][b][c] = dp[a-1][b][c]
+ dp[a-1][b-1][c]
+ dp[a-1][b][c-1]
- dp[a-1][b-1][c-1];
}
}
}
}
// 입력 처리
int a, b, c;
while (cin >> a >> b >> c) {
if (a == -1 && b == -1 && c == -1) break;
int ans;
if (a <= 0 || b <= 0 || c <= 0)
ans = 1;
else if (a > 20 || b > 20 || c > 20)
ans = dp[20][20][20];
else
ans = dp[a][b][c];
cout << "w(" << a << ", " << b << ", " << c << ") = " << ans << "\n";
}
return 0;
}
제공되는 데이터
실제 구현 단계
- 배열 초기화: base case를 미리 배열에 저장 (if문 체크 제거)
- 점화식 구현: 재귀식을 그대로 배열 인덱싱으로 변환
- 입력 처리: 범위 밖의 값들은 특별 규칙 적용
계산 복잡도
- 시간: O(21³) = O(9261) (한 번에 계산)
- 공간: O(21³) = O(9261개 정수) ≈ 18KB
재귀로 같은 상태를 반복 계산하는 것과 비교하면 엄청난 개선입니다.
다음 학습 계획
더 깊이 공부할 부분
Memoization vs Tabulation:
- 현재는 Tabulation (테이블 미리 채우기)
- Memoization (필요한 것만 계산)과 비교 분석
다른 DP 패턴:
- 2차원 DP (배낭 문제, 최장 부분수열)
- 1차원 DP (계단 오르기, 동전 문제)
- 각각 어떻게 위상 정렬로 보이는지
DAG와 DP의 일반화:
- 임의의 DAG에서 DP 설계
- 위상 정렬이 자동으로 DP 순서가 되는 이유
수치해석과의 연결:
- 3차원 격자 위의 함수 계산
- 경계값 문제와의 수학적 유사성
응용 아이디어
- 비슷한 구조의 문제들: 재귀 정의 → 상태 공간 분석 → DAG 확인 → DP 구현
- 실제 적용: 게임 AI (상태 공간 탐색), 최적화 문제
참고 자료
- 재귀 정의: 문제 설명에서 주어진 w(a,b,c)의 수학적 정의
- DP 변환: 점화식을 배열 접근으로 치환하는 기법
- 위상 정렬: 의존 관계를 만족하는 계산 순서의 이론적 기초