핵심 요약
- DP 문제에는 선형(타일링), 격자 경로, 배낭 문제(Knapsack), LIS 등 출제 빈도가 매우 높은 ‘족보’ 패턴이 존재합니다.
- 문제가 ‘최댓값’, ‘최솟값’, ‘경우의 수’를 묻는다면 DP일 확률이 90% 이상입니다.
- 그리디(욕심쟁이) 방식으로 풀었을 때 반례가 생긴다면, 즉시 DP로 전환해야 합니다.
- 입력 크기 N이 약 2,000 이하로 애매하게 작다면 O(N^2) 시간 복잡도를 허용하는 2차원 DP를 의심해봐야 합니다.
목차
1부에서 DP의 기본 개념(기억하며 풀기)과 구현 방법(Top-down, Bottom-up)을 다졌다면, 이제는 실전입니다. 코딩 테스트에 등장하는 DP 문제는 마치 수학 공식처럼 정해진 패턴이 있습니다. 처음에는 막막해 보여도 이 ‘5대 유형’의 코드 템플릿만 익혀두면, 문제의 껍데기만 바뀌어도 금방 눈치챌 수 있습니다. 각 유형별 특징과 바로 써먹을 수 있는 코드를 자세히 알아보겠습니다.
1. 시험에 무조건 나오는 DP 5대 유형
📌 유형 1: 선형 DP와 타일링 (마지막 행동 결정법)
DP의 가장 기초이자, 응용 변형이 가장 많은 유형입니다. ‘계단 오르기’, ‘2xN 타일 채우기’, ‘좌석 배치’ 등이 여기에 속합니다. 핵심은 “맨 마지막 칸(N)을 어떻게 채울 것인가?”를 기준으로 경우의 수를 나누는 것입니다.
- 판별법: 선택지가 ‘1칸 전(N-1)’ 또는 ‘2칸 전(N-2)’에서 오는 것 두 가지뿐일 때.
- 상황 예시:
- 계단: 1칸 오르기 vs 2칸 오르기
- 타일: 세로 타일(1개) 놓기 vs 가로 타일(2개) 놓기
- 좌석: 그냥 앉기(혼자) vs 옆 사람과 바꾸기(2명 1조)
- 점화식:
dp[i] = dp[i-1] + dp[i-2](피보나치 수열과 동일)
// [실전 코드] 타일링 / 계단 / 좌석 배치 (피보나치 패턴)
public int solveLinearDP(int n) {
if (n <= 2) return n; // 1이면 1가지, 2면 2가지
int[] dp = new int[n + 1];
dp[1] = 1;
dp[2] = 2;
// 3번째부터는 "마지막 행동"에 따라 합산
for (int i = 3; i <= n; i++) {
// dp[i-1]: 마지막에 1칸(세로/제자리) 처리한 경우
// dp[i-2]: 마지막에 2칸(가로/스왑) 처리한 경우
dp[i] = dp[i - 1] + dp[i - 2];
// (문제에 따라 모듈러 연산 % 1000000007 추가 필요)
}
return dp[n];
}
📌 유형 2: 최소/최대 비용 구하기 (1로 만들기)
단순한 경우의 수가 아니라, 특정 목표를 달성하는 데 필요한 '최소 연산 횟수'나 '최소 비용'을 구합니다. 여러 선택지 중 가장 효율적인 것을 골라야 하므로 Math.min() 함수가 필수적으로 사용됩니다.
- 상황: 정수 N을 1로 만드는데, 3으로 나누거나, 2로 나누거나, 1을 뺄 수 있다. 최소 횟수는?
- 핵심: 3가지 선택지(나누기 3, 나누기 2, 빼기 1) 중, 이전 단계에서 가장 횟수가 적었던 곳에서 오는 것이 이득입니다.
// [실전 코드] 1로 만들기
for (int i = 2; i <= n; i++) {
// 1. 기본 선택지: 1을 빼는 경우 (직전 숫자에서 1회 추가)
dp[i] = dp[i - 1] + 1;
// 2. 선택지: 2로 나누어 떨어지면, (i/2)번째 결과와 비교
if (i % 2 == 0) {
dp[i] = Math.min(dp[i], dp[i / 2] + 1);
}
// 3. 선택지: 3으로 나누어 떨어지면, (i/3)번째 결과와 비교
if (i % 3 == 0) {
dp[i] = Math.min(dp[i], dp[i / 3] + 1);
}
}
📌 유형 3: 2차원 격자 경로 찾기 (Grid)
체스판 같은 격자무늬 지도에서 왼쪽 위(0,0) 출발점부터 오른쪽 아래(N,M) 도착점까지 가는 문제입니다. 로봇은 보통 오른쪽이나 아래쪽으로만 움직일 수 있다는 제약이 있습니다.
- 핵심 논리: 특정 칸
(i, j)에 도착하려면, 반드시 위쪽(Up)이나 왼쪽(Left)에서 와야 합니다. 그 외의 길은 없습니다. - 점화식:
dp[i][j] = Math.max(위쪽 값, 왼쪽 값) + 내 위치의 보물
// [실전 코드] 최소 비용으로 이동하기
int[][] dp = new int[n][m];
// 시작점 초기화
dp[0][0] = map[0][0];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (i == 0 && j == 0) continue; // 시작점 제외
int fromUp = Integer.MAX_VALUE; // 위에서 오는 비용
int fromLeft = Integer.MAX_VALUE; // 왼쪽에서 오는 비용
// 위쪽 칸이 존재할 때만 값 가져오기
if (i > 0) fromUp = dp[i - 1][j];
// 왼쪽 칸이 존재할 때만 값 가져오기
if (j > 0) fromLeft = dp[i][j - 1];
// 둘 중 더 작은 비용을 선택하고, 현재 칸 비용 더하기
dp[i][j] = Math.min(fromUp, fromLeft) + map[i][j];
}
}
📌 유형 4: 배낭 문제 (Knapsack Problem) ⭐
DP의 '꽃'이라 불리는 가장 유명하고 중요한 유형입니다. 배낭의 무게 한도(K)가 정해져 있고, 가치가 다른 물건들이 있을 때 무엇을 담아야 가치의 합이 최대가 될까?를 고민하는 문제입니다.
- 테이블 정의:
dp[i][w]= i번째 물건까지 고려했고, 배낭 용량이 w일 때의 최대 가치. - 핵심 논리: 각 물건마다 선택권은 딱 두 개입니다. '넣는다' vs '안 넣는다'. 둘 중 더 이득인 쪽을 선택(Max)합니다.
// [실전 코드] 0/1 Knapsack
// i: 물건 번호 (1~N), w: 현재 배낭 무게 한도 (1~K)
for (int i = 1; i <= N; i++) {
for (int w = 1; w <= K; w++) {
// 1. 물건이 너무 무거워서 배낭(w)에 안 들어가는 경우
if (weight[i] > w) {
dp[i][w] = dp[i - 1][w]; // 이전 상태(i-1) 그대로 유지
}
// 2. 물건을 넣을 수 있는 경우
else {
// (안 넣는 경우) vs (넣고 남은 공간 채우기 + 내 가치) 중 큰 값
dp[i][w] = Math.max(dp[i - 1][w],
dp[i - 1][w - weight[i]] + value[i]);
}
}
}
📌 유형 5: 최장 증가 부분 수열 (LIS)
숫자가 나열된 수열에서, 순서를 유지하면서 숫자가 점점 커지는 부분 수열 중 가장 긴 길이를 찾는 문제입니다.
- 예시: {10, 20, 10, 30, 20, 50} -> 길이 4 (10, 20, 30, 50)
- 풀이법: 내 위치(i)보다 앞에 있는 숫자들(j)을 훑어보면서, "나보다 작은 숫자 중 가장 긴 수열을 가진 녀석" 뒤에 붙으면 됩니다.
// [실전 코드] LIS (O(N^2) 방식)
for (int i = 0; i < n; i++) {
dp[i] = 1; // 최소 길이는 나 혼자일 때 (1)
// 내 앞(0 ~ i-1)을 전부 확인
for (int j = 0; j < i; j++) {
// 나보다 작은 숫자를 발견하면
if (arr[j] < arr[i]) {
// 그 숫자의 길이 + 1과 현재 내 길이 중 큰 값 선택
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
2. 이 문제가 DP인지 어떻게 알죠? (판독법)
코딩 테스트 문제를 읽자마자 "이건 DP다!"라고 감을 잡을 수 있는 4가지 강력한 신호(Signal)가 있습니다.
🕵️♀️ 신호 1: 질문이 '최적'을 원한다
단순히 결과를 묻는 게 아니라, "가장 좋은(Optimal) 결과"를 원할 때 DP일 확률이 높습니다.
- 최대/최소: "최소 비용은?", "얻을 수 있는 최대 점수는?"
- 경우의 수: "목적지까지 가는 방법의 수는 몇 가지인가?"
- 가능 여부: "주어진 동전들로 합계 K원을 만들 수 있는가? (Yes/No)"
🕵️♀️ 신호 2: 선택이 미래에 영향을 준다 (연속성)
현재의 결정이 다음 단계의 선택지를 제한하거나 상태를 변화시킨다면 DP입니다. 예를 들어 "이전 집과 다른 색으로 칠해야 한다"는 조건이 있다면, 과거(앞집 색깔)를 기억해야 현재를 결정할 수 있으므로 DP입니다.
🕵️♀️ 신호 3: 그리디로 풀었는데 틀린다 (중요 ⭐)
많은 입문자가 "그냥 지금 당장 제일 좋은 거(비싼 거) 고르면 되는 거 아냐?"라고 생각합니다. 이것이 그리디(Greedy) 알고리즘입니다. 하지만 그리디로 풀었는데 예제 입력에서 오답이 나온다면? 100% DP로 선회해야 합니다.
[예시] 8원을 만드는 최소 동전 개수 (동전: 1원, 4원, 5원)
❌ 그리디 접근: 가장 큰 5원을 먼저 쓴다 -> 5원(1개) + 1원(3개) = 총 4개
⭕ DP 접근: 모든 경우를 따져본다 -> 4원(2개) = 총 2개 (정답!)
눈앞의 이득(5원)을 좇다가 최종 결과가 나빠지는 경우, 모든 경우를 따져보고 기록하는 DP가 유일한 해결책입니다.
🕵️♀️ 신호 4: 입력 크기(N)가 애매하다
컴퓨터는 1초에 약 1억 번 연산을 합니다. 시간 제한 1초 기준으로 N의 크기를 보고 힌트를 얻을 수 있습니다.
- N ≤ 20: 백트래킹, 완전탐색 (모든 경우를 다 해봐도 됨)
- N ≤ 100~2,000: O(N^3) 또는 O(N^2) 알고리즘인 DP일 확률이 매우 높음!
- N ≥ 100,000: O(N log N)이 필요하므로 1차원 DP 혹은 그리디일 가능성이 높음.
3. 입문자가 자주 하는 실수와 꿀팁
- 배열 범위(Index) 주의: 점화식에서
dp[i-2]를 참조한다면, 반복문은 반드시2이상부터 시작해야 에러(IndexOutOfBounds)가 나지 않습니다. - 자료형(long) 주의: '경우의 수' 문제는 답이 기하급수적으로 커집니다. 문제에서 "1,000,000,007로 나눈 나머지를 구하라"는 문구가 있거나 답이 21억을 넘을 것 같으면 무조건
long을 사용하세요. - 초기화 주의: 최솟값(Min Cost)을 구하는 문제라면
dp배열을 0으로 초기화하면 안 됩니다. 0이 최솟값이 되어버리기 때문입니다.Integer.MAX_VALUE같은 아주 큰 값으로 초기화해야Math.min()함수가 정상적으로 작동합니다.