동적 프로그래밍 실전 패턴 분석
크리스는 피보나치 수열을 통해 메모이제이션의 위력을 맛봤다.
"이제 모든 재귀 함수에 memo 배열만 넣으면 다 빨라지는 건가?"
하지만 세상은 그렇게 호락호락하지 않다.
병합 정렬(Merge Sort)도 재귀를 쓰지만, 거기엔 DP를 쓰지 않는다. 이유가 뭘까? 병합 정렬은 쪼개진 문제들이 서로 겹치지 않기(No Overlap) 때문이다. 왼쪽 절반 정렬하는 일과 오른쪽 절반 정렬하는 일은 완전히 별개다.
DP는 만능열쇠가 아니라, 특정 조건이 갖춰졌을 때만 발동하는 필살기다. 오늘은 코딩 테스트나 실무에서 "어? 이거 DP 각인데?"라고 눈치채는 감각을 길러보자.
1. DP의 시그널: 냄새를 맡아라
문제를 읽을 때 다음 키워드들이 보이면 DP를 강력하게 의심해야 한다.
그리고 가장 중요한 힌트, 문제를 쪼갰는데 **"작은 문제들이 계속 반복해서 등장"**해야 한다.
2. 대표 패턴 1: 계단 오르기 (Climbing Stairs)
문제: 당신은 계단을 오르고 있다. 한 번에 1계단 또는 2계단씩만 오를 수 있다. $N$번째 계단까지 오르는 방법은 총 몇 가지인가?
이 문제는 전형적인 DP다.
피보나치와 완전히 똑같은 구조다.
"마지막 도착지점 바로 전 단계가 어디지?"를 생각하면 식(점화식)이 나온다.
JavaScript
// dp[i] = i번째 계단까지 가는 방법의 수 // dp[i] = dp[i-1] + dp[i-2] function climbStairs(n) { const dp = [0, 1, 2]; // 1계단은 1가지, 2계단은 2가지(1+1, 2) for(let i = 3; i <= n; i++) { dp[i] = dp[i-1] + dp[i-2]; } return dp[n]; }
3. 대표 패턴 2: 배낭 문제 (Knapsack Problem)
DP의 끝판왕이자 가장 유명한 문제다.
문제: 도둑이 보석상에 들어갔다. 배낭에는 최대 10kg까지만 담을 수 있다. 보석마다 무게와 가격이 다르다. 배낭에 담을 수 있는 가장 비싼 가격의 합은 얼마인가?
이걸 단순히 "가격 순서대로" 담거나 "가벼운 순서대로" 담으면(Greedy) 최적의 답이 안 나온다.
이럴 때 **2차원 표(Grid)**를 그려서 작은 무게부터 차근차근 최댓값을 채워나가야 한다.
이 둘 중 **더 큰 값(Max)**을 선택해서 기록해 나간다. 이것이 DP의 정수다.
4. 그리디(Greedy)와의 차이점
많은 초보자가 그리디(탐욕) 알고리즘과 DP를 헷갈려 한다.
팁: 문제가 "현재의 선택이 미래에 영향을 주지 않는다"면 그리디, "영향을 준다"면 DP일 확률이 높다.
5. 4장을 마치며: 똑똑한 코딩의 시작
우리는 동적 프로그래밍을 통해 "무식하게 다 해보기(Brute Force)"를 "효율적으로 다 해보기"로 바꾸는 법을 배웠다.
이제 알고리즘의 4대 천왕(정렬, 검색, 그래프, DP)을 모두 맛봤다.
하지만 아직 다루지 않은 녀석이 있다.
"지금 당장 최선이면 그냥 직진해!"라고 외치는 쿨가이, 탐욕(Greedy) 알고리즘이다. DP를 쓰기엔 너무 무겁고, 답이 뻔히 보일 때 쓰는 속도전의 명수다.
5장 탐욕 알고리즘 - 1. 탐욕 알고리즘이란? 편에서 계속된다.