Dynamic Programming이 필요할 때를 아는 방법

Source: Dev.to

Originally published on LeetCopilot Blog

추측을 멈추세요. 문제에 DP가 필요하다는 정확한 신호를 알아두면 30분을 무작정 브루트포스에 낭비하지 않을 수 있습니다.

LeetCode 문제를 바라보고 있습니다. 난이도는 Medium이고, 카운팅이나 최적화와 관련돼 있습니다. 그런데 이게 DP일까요?
탐욕적인 접근을 20분 동안 시도했지만 17번째 테스트 케이스에서 실패합니다. 재귀를 시도했지만 스택 오버플로우가 발생합니다. 결국 해설 탭을 엽니다:

“이것은 전형적인 동적 프로그래밍 문제다.”

당연히 그렇죠. 그런데 코딩하기 전에 어떻게 알 수 있었을까요?

이 가이드는 코드를 입력하기 전에 DP 문제를 인식하는 체크리스트를 제공합니다.

TL;DR

• DP 문제는 두 가지 특징을 가집니다: 중복되는 부분문제(overlapping subproblems) + 최적 부분구조(optimal substructure).
• 주의해야 할 키워드: “경우의 수를 세어라”, “최소/최대 경로”, “가장 긴/짧은 부분수열”.
• 재귀 테스트: 브루트포스 재귀가 같은 (state)를 여러 번 계산한다면 DP입니다.
• 탐욕 테스트: 각 단계에서 지역 최적을 선택해도 전체 최적을 보장하지 못한다면, 이는 대부분 DP입니다.
• 자주 등장하는 카테고리: 피보나치형 시퀀스, 격자 경로, 배낭 문제 변형, 문자열/부분수열 문제, “선택하거나 건너뛰기” 형태의 결정 트리.

두 가지 필수 속성

동적 프로그래밍은 **“캐시가 있는 똑똑한 재귀”**에 불과합니다. 이 두 가지 특성이 없으면 DP가 아닙니다.

속성 1: 중복되는 부분문제 (Overlapping Subproblems)

큰 문제를 풀 때 같은 작은 문제를 반복해서 풉니다.

예시: 피보나치.

• fib(5)를 계산하려면 fib(4)와 fib(3)이 필요합니다.
• fib(4)를 계산하려면 다시 fib(3)이 필요합니다.
• fib(3)을 두 번 계산하게 됩니다.

테스트: 일부 노드가 반복되는 재귀 트리를 그릴 수 있나요?
가능하면 → 중복되는 부분문제가 존재 → DP를 적용할 수 있습니다.

속성 2: 최적 부분구조 (Optimal Substructure)

전체 최적 해는 부분문제들의 최적 해로부터 구성될 수 있습니다.

예시: 최단 경로.
A에서 C로 가는 최단 경로가 B를 거친다면, A에서 B로 가는 경로 역시 B에 대한 최단 경로여야 합니다.

반례: 가장 긴 단순 경로(노드를 재방문할 수 없는 경우).
A에서 C로 가는 가장 긴 경로가 B를 거친다고 해도, A에서 B로 가는 가장 긴 경로를 사용하면 나중에 필요한 노드가 차단될 수 있습니다.
최적 부분구조가 없으므로 DP가 통하지 않습니다.

키워드 레드 플래그 (문제 설명 힌트)

다음과 같은 문구가 나오면 거의 확실히 DP입니다:

문제가 카운트, 최소/최대, 혹은 가장 긴/짧은 무언가를 구하라고 하면 DP를 떠올리세요.

재귀 연기 테스트 (Recursion Smoke Test)

간단한 현장 테스트:

1. 브루트포스 재귀 해결법을 작성한다.
2. 작은 입력에 대해 재귀 트리를 그린다 (예: n = 4).

확인: 같은 매개변수가 여러 번 등장하나요?

예시: Coin Change

solve(amount = 11) → solve(10), solve(9), solve(6)
solve(10) → solve(9), …

solve(9)가 서로 다른 가지에서 두 번 나타납니다 → 중복되는 부분문제 감지 → 메모이제이션(DP) 적용.

모든 부분문제가 고유하면 단순 재귀(예: 트리 순회)이며 DP가 아닙니다.

흔히 보는 DP 문제 유형

1. 피보나치형 시퀀스

패턴: dp[i]가 dp[i‑1], dp[i‑2], …에 의존한다.
예시: Climbing Stairs, House Robber, Decode Ways.

2. 격자 탐색

패턴: dp[row][col]가 위쪽 혹은 왼쪽 셀에 의존한다.
예시: Unique Paths, Minimum Path Sum, Dungeon Game.

3. 배낭 변형

패턴: 각 아이템에 대해 “가져갈지 말지”를 결정한다.
예시: 0/1 Knapsack, Partition Equal Subset Sum, Target Sum.

4. 문자열 / 부분수열

패턴: dp[i][j]가 인덱스 i 부터 j 까지의 부분문제 해를 나타낸다.
예시: Longest Palindromic Substring, LCS, Edit Distance.

5. 결정 트리 (선택하거나 건너뛰기)

패턴: 각 원소에 대해 포함하거나 제외한다.
예시: Coin Change, Combination Sum, Word Break.

DP를 쓰면 안 되는 경우

1. 탐욕법이 통할 때

일부 최적화 문제는 “탐욕 선택 속성”을 가지고 있어 지역 최적이 전체 최적이 됩니다.
예시: Activity Selection, Jump Game(일부 경우).
테스트: 매 단계에서 최선 선택을 하면 전체 최선이 보장되는가? 그렇다면 탐욕법을 사용하세요.

2. 중복되는 부분문제가 없을 때

모든 재귀 호출이 고유하면 캐시가 도움이 되지 않는다.
예시: 가지치기 없이 모든 순열·조합을 생성하는 경우.

3. 구조가 없는 NP‑Complete 문제

예를 들어 임의 그래프의 Traveling Salesman 문제는 효율적인 DP 해법이 존재하지 않는다.

단계별 인식 흐름

문제를 읽을 때 다음 체크리스트를 머릿속으로 돌리세요:

1. 카운트/최소/최대/가장 긴을 요구하나요? → +1 DP 포인트.
2. 재귀적으로 표현할 수 있나요? → +1 DP 포인트.
3. 부분문제가 겹치나요? → +1 DP 포인트.
4. 탐욕법이 실패하나요? → +1 DP 포인트.

3점 이상이면 거의 확실히 DP 문제입니다.

인식 능력 키우는 방법

• 클래식 DP 문제 20개 이상 풀기 (예: Blind 75, Grind 75).
• 문제에 라벨 붙이기: “이건 격자 DP다.” “이건 배낭 변형이다.”
• 일주일 뒤에 다시 풀어보기: 패턴을 다시 식별할 수 있는지 확인.

LeetCopilot’s Study Mode 같은 도구는 문제 설명만 보고 패턴을 맞추는 플래시카드를 자동 생성해 줍니다.

FAQ

Q: 문제는 DP와 탐욕을 동시에 가질 수 있나요?
A: 드물지만 가능합니다(예: Jump Game II). 보통은 한 방법이 명확히 더 좋습니다.

Q: 확신이 서지 않으면?
A: 브루트포스 재귀부터 시작하세요. 시간이 초과되고 호출이 반복되는 걸 보면 메모이제이션을 하면 됩니다—그게 DP입니다.

Q: DP가 항상 가장 빠른 해법인가요?
A: 반드시 그렇지는 않습니다. 경우에 따라 탐욕법이나 최적화된 BFS가 더 빠를 수 있습니다. DP는 구조를 파악했을 때 가장 직관적인 접근법이 되는 경우가 많습니다.

Q: 상태 차원을 어떻게 정하나요?
A: “부분문제 사이에 무엇이 변하나요?”를 물어보세요. 하나의 인덱스이면 1D DP, 두 인덱스 혹은 (인덱스, 남은 용량)이라면 2D DP가 됩니다.

Q: top‑down과 bottom‑up 중 어느 쪽을 먼저 써야 하나요?
A: top‑down(메모이제이션)이 구현하기 쉽습니다. bottom‑up(테이블링)은 메모리 사용이 효율적이고 인터뷰에서는 가독성이 좋으니 선호됩니다.

결론

DP를 인식하는 것은 마법이 아니라 패턴 매칭입니다.

• 최적화·카운팅 질문을 찾으세요.
• 재귀 트리에서 중복 호출을 확인하세요.
• 최적 부분구조가 존재하는지 검증하세요.

연습을 통해 “방법의 수를 구하라”는 문장을 보자마자 “아, DP다. 1D 배열, 아마 피보나치형.” 라고 생각하게 될 것입니다.

그때 LeetCode는 추측이 아니라 체계적인 문제 해결이 됩니다.

코딩 인터뷰 준비와 LeetCode 패턴 마스터를 도와줄 AI 비서가 필요하다면 LeetCopilot을 확인해 보세요.