DP 가이드 (11/11)

이전 편: [코딩테스트] 10. 배낭 문제

이 문서가 시리즈의 마지막 편입니다.

DP 유형별 패턴 시리즈

선형 DP · 격자 DP · LIS · 배낭 문제 · 실전 패턴과 면접 대비

DP 가이드 : 기본 개념 → 설계 전략 → 유형별 패턴

유형을 익혔으면 실전에서 어떻게 접근할지 정리해보자. DP 문제를 처음 보고 막막할 때 쓰는 체크리스트와, 면접에서 자주 나오는 질문을 다룬다.

실전 접근 체크리스트

DP 문제라는 판단이 서면 다음 순서로 진행한다.

flowchart TD A["문제 읽기"] --> B{"최적값/경우의수\n구하는가?"} B -->|"예"| C["상태 정의\ndp[i]에 뭘 저장?"] B -->|"아니오"| Z["DP가 아닐 수 있음"] C --> D["점화식 도출\n마지막 결정 기준으로 경우 나누기"] D --> E["초기값 설정\nBase case 직접 채우기"] E --> F["탐색 순서 결정\n의존 방향 확인"] F --> G["작은 예시로 검증\n손으로 계산"] G --> H["코드 작성"]

G단계(손 계산 검증)를 절대 생략하지 마라. 점화식이 틀렸을 때 코드를 다 짜고 나서 발견하면 훨씬 시간이 든다.

DP인지 판별하는 신호

모든 문제가 DP는 아니다. 다음 신호가 보이면 DP를 고려한다.

  • "최대", "최소", "최적"이라는 단어
  • "경우의 수", "방법의 수"
  • "~을 만들 수 있는가", "~에 도달 가능한가" (가능 여부)
  • 부분 구조가 반복되는 느낌 (같은 계산을 여러 번 하고 있는 것 같다)

상태 정의 막힐 때

dp[i]를 뭐로 정의할지 감이 안 잡힌다면 이 방법을 써보자.

  • 최종 답을 먼저 특정 dp 값으로 표현해본다 (dp[N]이 답이 되려면?)
  • 작은 예시 (n=3, n=4)를 손으로 계산하고, 패턴을 일반화한다
  • "마지막 원소가 arr[i]일 때" 처럼 조건을 달아서 dp[i]를 한정해본다

자주 하는 실수

  • 초기값을 0으로 : 최솟값 문제에서 dp = 0으로 초기화하면 안 됨. INF로
  • 경계 처리 누락 : 2D 격자에서 첫 행/열은 별도 처리
  • 탐색 순서 역전 : dp[i]가 참조하는 값이 아직 계산되지 않은 상태
  • 배낭 순회 방향 : 0/1 배낭이면 역순, 무한 배낭이면 순방향
  • 답이 dp[N]이 아닌 경우 : LIS처럼 dp 배열 전체의 최댓값이 답인 경우도 있음

면접 질문

Q. DP와 분할 정복의 차이는?

둘 다 큰 문제를 작은 문제로 쪼갠다. 차이는 중복 부분 문제 유무다. 분할 정복(병합 정렬 등)은 하위 문제가 겹치지 않아 결과를 저장할 필요가 없다. DP는 같은 하위 문제가 반복 등장하므로 저장해서 재사용한다.

[!QUESTION] Q. Top-down과 Bottom-up 중 어느 걸 쓰나?

코딩테스트에서는 Bottom-up이 기본이다. 스택 오버플로우가 없고 공간 최적화가 쉽다. 문제 구조가 복잡해서 탐색 순서를 결정하기 어려울 때는 Top-down이 더 자연스럽다.

[!QUESTION] Q. 메모이제이션은 DP인가?

맞다. Top-down DP다. 재귀 구조를 유지하면서 계산 결과를 저장하는 방식이다.

[!QUESTION] Q. 시간복잡도는 어떻게 구하나?

(상태의 수) × (각 상태를 계산하는 데 걸리는 시간). 1D DP에서 상태가 N개이고 각 상태 계산이 O(1)이면 O(N). 배낭 문제는 상태가 N×W개이고 각 상태 계산이 O(1)이면 O(NW).

[!QUESTION] Q. DP로 풀 수 없는 문제도 있나?

최적 부분 구조나 중복 부분 문제 조건 중 하나라도 없으면 DP를 적용할 수 없다. 예를 들어 최장 경로 문제(사이클 없는 그래프 제외)는 최적 부분 구조가 성립하지 않아 DP로 못 푼다.