코딩테스트 DP(동적계획법) 뇌정지 탈출법: 실전에서 점화식이 안 떠오를 때 던져야 할 7가지 질문

코딩테스트장에서 DP(동적 계획법) 문제를 만나면 숨이 턱 막힙니다. 머릿속으로는 '이거 분명 어디서 본 패턴인데' 싶으면서도, 정작 손은 키보드 위에서 갈 길을 잃고 헤매죠. 시간에 쫓기다 보면 결국 익숙한 DFS, BFS나 완전 탐색으로 회귀하게 되고, 어김없이 '시간 초과'라는 붉은 글씨를 마주하게 됩니다. 왜 우리는 실전에서 DP를 눈앞에 두고도 알아보지 못하거나, 알아봐도 손을 대지 못할까요?

 

이유는 간단합니다. DP는 공식 암기로 풀리는 알고리즘이 아니라, 문제를 바라보는 '관점의 전환'을 요구하기 때문입니다. 수많은 코테 탈락의 고배를 마시며 축적한 경험을 바탕으로, 실전에서 뇌정지가 왔을 때 탈출구 역할을 해줄 7가지 질문과 그 뒤에 숨겨진 실무적 트레이드오프를 가감 없이 공유합니다. 이 글은 흔한 문제 풀이 팁이 아닙니다. 코딩테스트라는 실전 압박 속에서 당신의 합격을 견인할 서바이벌 가이드입니다.

1. 단계적 확장: n을 1씩 늘릴 때 규칙성이 깨지는가?

많은 이들이 DP를 판별할 때 '최적 부분 구조' 같은 교과서적 단어에 매몰됩니다. 하지만 실전에서 그런 추상적인 개념은 와닿지 않습니다. 가장 직관적인 방법은 입력 데이터의 크기 n을 1부터 강제로 늘려가며 손으로 직접 그려보는 것입니다. 대형마트 오픈런 줄을 설 때 앞사람의 이동이 뒷사람에게 그대로 영향을 주듯, n=1, n=2, n=3, n=4일 때의 결과가 그다음 상태의 빌딩 블록이 되는지 확인해야 합니다.

 

만약 n=4의 답을 구하는 과정에 n=3일 때 구해둔 최적의 선택지가 고스란히 재사용된다면, 이는 완벽한 DP의 징후입니다. 반대로 n이 커질 때마다 이전의 결과가 완전히 뒤엎어지고 처음부터 다시 판을 짜야 한다면, 그 문제는 그리디나 완전 탐색, 혹은 정렬을 의심해야 합니다. 이건 직접 문제를 손으로 3단계만 써봐도 체감이 확 됩니다. 규칙성이 누적되는지, 아니면 파괴되는지 그것만 먼저 확인하십시오.

2. 중복 호출의 늪: 호출 트리를 그렸을 때 하위 노드가 겹치는가?

두 번째로 던져야 할 질문은 "이 문제를 단순 재귀(Naive Recursion)로 풀었을 때 어떤 대가를 치르는가?"입니다. 머릿속으로 함수 호출 트리(Call Tree)를 가볍게 시각화해 보세요. 피보나치 수열이 대표적입니다. $f(5)$를 구하기 위해 $f(4)$와 $f(3)$을 부르고, $f(4)$는 다시 $f(3)$과 $f(2)$를 부릅니다. 이 과정에서 $f(3)$이라는 동일한 연산이 여러 서브 트리에서 중복으로 등장합니다.

 

이처럼 이미 계산했던 결과를 또 계산하느라 CPU를 낭비하는 구조라면, 메모리를 조금 더 써서 시간 복잡도를 획기적으로 낮추는 DP의 '메모이제이션(Memoization)'이 정답입니다. 만약 호출 트리 상에서 중복되는 노드가 단 하나도 없고 매번 새로운 상태만 탐색한다면, 그건 DP가 아니라 백트래킹(Backtracking)이나 순수한 분할 정복(Divide and Conquer)으로 풀어야 하는 문제입니다.

데이터센터 서버 랙과 연산 프로세서 - 생성형 AI 이미지

3. 문제의 요구사항: 최댓값, 최솟값, 혹은 '경우의 수'인가?

출제자의 의도는 문제의 명사보다 '동사'와 '형용사'에 담겨 있습니다. 문제 지문 맨 마지막 줄을 보십시오. "가장 최소가 되는 비용을 구하시오", "얻을 수 있는 최대 가치를 출력하시오", "도달할 수 있는 방법의 가짓수를 구하시오"로 끝나나요? 그렇다면 심증은 90% 이상 DP로 기웁니다.

 

DP는 본질적으로 최적화 문제(Optimization Problem)와 카운팅 문제(Counting Problem)를 해결하는 데 특화되어 있습니다. 매 순간의 최적 선택이 전체의 최적을 보장하지 않는 복잡한 제약 조건 속에서, 모든 가짓수를 고려하되 중복을 제거하며 효율적으로 최종 답을 도출하는 도구이기 때문입니다. "특정 조건을 만족하는 조합을 모두 나열하라"가 아니라, 그 조합의 '개수'나 '최적값'만 원한다면 뒤도 돌아보지 말고 DP 테이블을 설계할 준비를 해야 합니다.

4. 제약 조건의 힌트: 입력 크기 N이 오묘하게 제한되어 있는가?

코딩테스트에서 변수의 범위는 정답 알고리즘의 시간 복잡도를 알려주는 완벽한 이정표입니다. 만약 문제에서 요구하는 입력 크기 N이 대략 1,000에서 10,000 사이로 주어졌다면 이는 매우 강력한 힌트입니다. 시간 제한이 보통 1초~2초 내외로 주어지는 환경에서, 완전 탐색의 $O(2^N)$이나 $O(N!)$은 당연히 터집니다. 반면 $O(N \log N)$이나 O(N^2) 수준의 알고리즘은 통과할 수 있죠.

 

2차원 DP 테이블을 채우는 시간 복잡도는 보통 $O(N \times M)$입니다. N=1,000, M=1,000일 때 연산 횟수는 1,000,000번 수준에 불과하므로, O(N^2) DP 알고리즘은 아주 여유롭게 합격 목걸이를 가져옵니다. 반대로 N이 20 이하로 극단적으로 작다면 백트래킹이나 비트마스킹 완전 탐색을, N이 10^7 이상으로 너무 크다면 $O(N)$이나 $O(\log N)$인 그리디 또는 이분 탐색을 먼저 의심해야 합니다.

5. 상태 정의의 경계: dp[i]의 'i'에 무엇을 담을 것인가?

DP를 풀 때 가장 많은 개발자가 무너지는 지점이 바로 이곳입니다. "배열은 만들었는데, 여기에 뭘 저장해야 하지?" 상태 정의(State Definition)가 모호하면 그 뒤에 나오는 점화식은 전부 모래성에 불과합니다. 명확한 문장으로 정의해야 합니다. 예를 들어 "dp[i]는 i번째 계단까지 올라왔을 때 얻을 수 있는 점수의 최댓값"처럼 말이죠.

 

만약 1차원 배열만으로 현재 상태를 온전히 표현할 수 없다면, 과감하게 차원을 늘려야 합니다. "dp[i][j]는 i번째 물건까지 고려했고, 현재 배낭의 남은 무게가 j일 때의 최대 가치"처럼 변수를 추가하는 것입니다. 단, 차원이 늘어날 때마다 메모리 사용량은 기하급수적으로 증가합니다. 실무나 고난도 코테에서는 메모리 제한(보통 128MB~512MB)을 초과하는 슬라이딩 윈도우(Sliding Window) 기법의 필요성도 이 단계에서 결정됩니다.

6. 점화식 유도: 마지막 선택의 순간으로 돌아가 역산할 수 있는가?

상태를 정의했다면 이제 핵심인 점화식(Recurrence Relation)을 세울 차례입니다. 점화식을 가장 쉽게 세우는 비결은 '마지막 단계'에 서서 바로 전 단계를 바라보는 것입니다. 내가 지금 i번째 위치에 서서 최종 결정을 내리기 직전이라고 가정해 봅시다. 내가 이 자리에 오기 위해 바로 직전에 할 수 있었던 행동은 무엇인가요?

 

계단 오르기 문제를 예로 들면, i번째 계단에 서기 전의 상태는 두 가지뿐입니다. i-1번째 계단에서 1칸 걸어왔거나, i-2번째 계단에서 2칸 뛰어왔거나. 이 두 갈래 길 외에는 존재하지 않습니다. 그렇다면 i번째의 최적값은 아래와 같이 유도됩니다.

 

모든 경우의 수를 빠짐없이 나열하되, 각 상태가 서로 독립적이고 중복되지 않도록(Mutually Exclusive, Collectively Exhaustive) 쪼개어 수식으로 연결하는 연습이 필요합니다. 손으로 예제 입력값 몇 개를 대입해 보며 점화식이 들어맞는지 반드시 검증하십시오.

7. 구현 패러다임: Top-down(재귀)과 Bottom-up(반복문) 중 무엇이 유리한가?

점화식까지 나왔다면 마지막 선택만 남았습니다. 아래를 향해 내려갈 것인가, 밑바닥부터 쌓아 올릴 것인가? 두 방식은 명확한 트레이드오프를 가집니다. 프로젝트 아키텍처를 설계할 때 생산성과 성능을 저울질하는 것과 같습니다.

구현 방식	장점	단점 / 위험 요인
Top-down (재귀 + Memoization)	점화식을 코드로 직관적으로 옮기기 쉽다. 필요한 상태만 탐색하므로 가끔 더 빠르다.	함수 호출 오버헤드가 크다. 파이썬 등에서는 Stack Overflow 위험이 상존한다.
Bottom-up (반복문 + Tabulation)	재귀 오버헤드가 없어 성능이 안정적이고 예측 가능하다. 메모리 최적화가 쉽다.	테이블을 채워나갈 인덱스의 순서와 초기값 설정을 잘못하면 디버깅이 지옥으로 변한다.

만약 가독성과 빠른 구현이 우선이고 N의 크기가 스택 제한을 넘지 않을 정도로 안전하다면 Top-down이 좋습니다. 하지만 코딩테스트 플랫폼의 제한이 엄격하고 효율성 점수를 극대화해야 한다면, 처음부터 반복문으로 빈 테이블을 채워나가는 Bottom-up 방식을 완벽하게 숙달하는 것을 권장합니다.

DP 점화식은 잘 세웠는데 계속 틀립니다. 뭐가 문제인가요?"

현업 후배들이나 취준생들에게 가장 많이 받는 질문 중 하나입니다. 수식도 완벽하고 코드 구조도 맞는데 '틀렸습니다'를 마주한다면, 99%는 초기값(Base Case) 설정 오류이거나 인덱스 범위 초과(Out of Bounds), 혹은 자료형 오버플로우 때문입니다.

 

DP 테이블의 0번째, 1번째 칸에 채워 넣는 초기값은 점화식이라는 엔진을 돌리기 위한 연료입니다. 문제 조건에서 N=1이거나 N=2일 때의 예외 처리를 누락하면, 반복문이 돌면서 엉뚱한 가비지 데이터(Garbage Data)를 참조하거나 배열 인덱스 음수를 찌르게 됩니다. 또한, 방법의 수를 구하는 문제에서 결과값을 특정 수(예: 1,000,000,007)로 나누라는 조건이 있다면, 마지막 출력 직전이 아니라 DP 테이블을 채우는 매 연산 과정마다 나머지 연산(% 모듈러)을 적용해야 자료형의 한계를 넘어 쓰레기 값이 저장되는 참사를 막을 수 있습니다.

결국 어떤 선택을 해야 하는가?

코딩테스트장에서 DP가 떠오르지 않을 때, 이 7가지 질문을 머릿속으로 빠르게 스캔하십시오. 문제 분류가 눈에 보이기 시작하면 막연한 공포감은 사라집니다. 실전에서 살아남기 위한 합격 시나리오는 다음과 같이 압축됩니다.

• 입력이 작고 최적값을 구하라면: 일단 완탐이나 재귀로 접근해보고 중복 호출이 발생하는지 체크한 뒤, 메모이제이션 배열을 얹어 Top-down DP로 변환하십시오.
• 입력이 1,000 이상으로 크고 정밀한 제어가 필요하다면: N=1부터 규칙성을 손으로 찾아낸 뒤, 빈 1차원/2차원 배열을 선언하고 반복문으로 밑바닥부터 채우는 Bottom-up DP를 선택하십시오.
• 구현 도중 값이 꼬인다면: 점화식을 의심하기 전에 본인이 설정한 초기값(Base Case)의 하드코딩 수치와 루프의 시작 인덱스가 올바른지 눈 불을 켜고 디버깅하십시오.

알고리즘 공부는 단순히 정답 코드를 외우는 과정이 아닙니다. 제약 조건 속에서 최선의 트레이드오프를 선택하는 훈련이며, 이는 고스란히 실무에서 대규모 트래픽과 리소스 제한을 다루는 백엔드 아키텍처 설계 능력으로 이어집니다. 시험장에서 당황하지 말고, 스스로에게 이 7가지 질문을 던지며 한 단계씩 논리를 풀어가십시오. 건투를 빕니다.

 

코테용 이분탐색은 다르다! 무한 루프 없는 매개 변수 탐색 실전 템플릿