[코드 인터뷰 대비 시리즈 #6] 동적 프로그래밍(DP) 문제 접근 패턴 정리

여러분, 알고리즘 인터뷰에서 동적 프로그래밍(DP) 문제를 접하면 많은 지원자가 “복잡하고 난해해”라며 당황하기 쉽습니다. DP는 문제를 작은 하위 문제(subproblem)로 나누고, 하위 문제의 해를 저장(memoization)하거나 테이블(tabulation)로 관리하여 중복 계산을 제거하는 기법입니다. 제대로 이해하고 패턴을 파악하면 DP 문제도 체계적으로 접근할 수 있으며, 면접 중에도 당황하지 않고 논리적으로 문제를 풀어나갈 수 있습니다.

이번 글에서는 DP 문제를 만났을 때 어떤 접근 방법을 사용할지, 점화식(Recurrence Relation)을 어떻게 세우는지, 탑다운(Top-Down)과 바텀업(Bottom-Up) 접근 차이, 코너 케이스 처리, 복잡도 분석, 그리고 면접 상황에서 이 모든 과정을 어떻게 설명하면 좋을지 단계별로 매우 구체적으로 다뤄보겠습니다. 또한 필요 시 std::expected, std::format, coroutine, Ranges 등의 추가 아이디어나 조건부 로직, 비동기 처리 가능성까지 언급해볼게요.

1. DP 문제를 접근하기 전: 패턴 인식과 점화식 수립 연습

DP 문제에서 가장 중요한 첫 단계는 문제를 하위 문제로 나누는 패턴을 인식하는 것입니다. DP는 “큰 문제를 작은 문제로 나누고, 그 해를 메모이제이션해서 중복 계산을 피한다”는 원리가 핵심인데, 이를 위해 다음과 같은 질문을 던져보세요.

1. “이 문제는 부분 구조(substructure)를 가지고 있는가?”
   즉, 문제를 어떤 방식으로 쪼개어도 동일한 형태의 하위 문제가 등장하는지 확인합니다.
2. “중복되는 하위 문제가 있는가?”
   브루트포스로 풀면 동일한 하위 문제를 여러 번 계산해야 하는 경우, DP가 유용합니다.
3. “점화식(Recurrence)을 어떻게 세울까?”
   DP의 핵심은 점화식을 정의하는 것입니다. 예를 들어 최대 부분합 문제에서 dp[i] = max(dp[i-1]+arr[i], arr[i]) 형태로 i번째 원소를 포함하는 최대 부분합을 i-1번째에서 유도할 수 있다면 DP 패턴을 잡은 것입니다.

이러한 과정은 단순히 “아 DP 써야지”로 끝나는 게 아니라, 실제 면접에서 문제를 처음 본 뒤 “이 문제를 i번째 상태까지 계산한다고 하면, i-1번째 상태에서 어떻게 유도하지?”라고 생각하는 사고 과정을 면접관 앞에서 verbalize하는 데 중요합니다.

2. 탑다운(Top-Down) vs 바텀업(Bottom-Up) 접근

DP 구현에는 크게 두 가지 스타일이 있어요.

1. 탑다운(Top-Down) + 메모이제이션:
   재귀 함수를 사용해 원하는 값 dp(n)을 구할 때, 재귀 중간에 dp(k) 값을 요청하면 memo[k]를 확인하고, 없으면 계산 후 저장. 이 방식은 구현이 직관적이지만, 재귀 스택 제한과 메모리 접근 패턴을 고려해야 합니다.
2. 바텀업(Bottom-Up) + 테이블(tabulation):
   작은 문제부터 시작해 dp 배열을 채워나가며 최종 dp[n]까지 계산하는 방식. 재귀 없이 반복문으로 해결 가능하며, 대개 O(N) 또는 O(N*M) 형태로 명확한 테이블 채우기 과정을 갖습니다.

면접에서 탑다운/바텀업 중 하나를 고르거나 둘 다 가능하다고 언급한 뒤, “이 문제는 재귀적 정의가 직관적이므로 탑다운 쓰겠습니다” 혹은 “반복문으로 테이블 채우기가 쉬우니 바텀업을 선택하겠습니다”라고 설명하면 됩니다. 코너 케이스로 n=0일 때 dp[0]=... 같은 초기값 설정을 명확히 하는 것도 중요합니다.

3. 예제 문제로 DP 접근 패턴 익히기

예제 1: 피보나치 수(Fibonacci Numbers)
가장 전형적인 DP 예제입니다. 피보나치는 F(n)=F(n-1)+F(n-2)로 정의되어 점화식이 매우 간단하죠.

단계별 사고 과정:

• 문제: n번째 피보나치 수를 O(n) 시간에 구하라.
• 아이디어: dp[0]=0, dp[1]=1로 시작해 dp[i]=dp[i-1]+dp[i-2] 반복으로 O(n)에 계산.
• 코너 케이스: n=0이면 0 반환, n=1이면 1 반환.
• 면접 설명: “점화식이 간단하고 중복 계산 제거로 O(n)에 가능. 메모리 O(n)이지만 O(1)로 최적화 가능(이전 두 값만 저장).”
• 예를 들어 Baekjoon 피보나치 수 문제나 LeetCode "Fibonacci Number" 문제로 연습.

예제 2: 최대 부분합(Maximum Subarray) 문제
이 문제는 [LeetCode](https://leetcode.com) Maximum Subarray로 매우 유명한데, dp[i]를 “i번째 원소를 포함하는 최대 부분합”으로 정의할 수 있습니다.

단계별 사고 과정:

• 문제: 배열에서 연속된 부분 배열 중 합이 최대인 값을 구하라.
• 아이디어: dp[i]=max(dp[i-1]+arr[i], arr[i])
  • 여기서 dp[i-1]을 써서 i번째 원소 포함 최대합을 i-1에서 유도.
• 초기값: dp[0]=arr[0].
• 전체 최대합은 모든 dp[i] 중 최대값.
• 면접 설명: “O(n)에 해결, 추가 메모리 O(n)이지만 dp값만 있으면 되므로 O(1)으로 축소 가능. 코너 케이스로 빈 배열일 경우 문제에서 어떻게 정의하는지 확인(보통 빈 배열 없다 가정하거나 arr 크기≥1).”
• 이 문제에서 std::expected로 빈 배열 시 에러 반환 가능. 로깅(std::format)으로 각 단계 dp[i]값 출력해 디버깅할 수도 있어요.

4. 문자의 DP 문제(문자열 DP), 경로 DP

문자열 DP 문제나, 격자(Grid) 상 경로 문제에서도 DP가 빈번히 사용됩니다.

문자열 DP 예: 편집 거리(Edit Distance)
LeetCode "Edit Distance" 문제나 Baekjoon 편집 거리 문제를 생각해볼까요?

단계별 사고 과정:

• 문제: 두 문자열 A,B가 주어졌을 때 A를 B로 바꾸는 최소 연산 횟수(삽입, 삭제, 교체).
• 아이디어: dp[i][j] = A[0..i-1]을 B[0..j-1]로 바꾸는 최소 연산 수.
  • 점화식:
    • 만약 A[i-1] == B[j-1]이면 dp[i][j]=dp[i-1][j-1]
    • 아니면 삽입, 삭제, 교체 중 최솟값+1
• 초기값: dp[0][j]=j (빈 문자열에서 B[0..j-1] 만들려면 j번 삽입), dp[i][0]=i (A[0..i-1]에서 빈문자열 만들려면 i번 삭제).
• 면접 설명: “O(NM) 시간, N=M=문자열 길이. 코너 케이스: 빈 문자열 처리 명확히. 로깅으로 dp 테이블 상태 확인 가능.”

이 문제는 복잡도 O(NM)이고, 면접에서 문자열 변환 문제를 DP로 해결했다고 말하면 높은 평가를 받을 수 있습니다.

격자 경로 DP 예: 최단 경로 문젠데 비용이 음수 없고 단순히 오른쪽/아래로만 이동하는 경우
Programmers "등굣길" 문제나 Baekjoon "오르막 수"와 유사 문제들.

단계별 사고 과정:

• 문제: N×M 격자에서 (0,0)→(N-1,M-1)로 가는 경로 수/비용 최소/최대 문제 등.
• 아이디어: dp[i][j] = (i,j)까지 오는 데 필요한 최소비용 또는 경로 수.
• 점화식: dp[i][j]=dp[i-1][j]+dp[i][j-1] (경로 수 문제라면 두 방향에서 오는 경로 수 합)
• 코너 케이스: i=0이나 j=0 행/열 처리(테두리 조건).
• 면접 설명: “이 문제는 dp 테이블 채우기로 O(NM)에 해결, 메모이제이션보다는 바텀업 접근이 직관적이고, 빈칸이나 장애물 유무에 따라 조건부로 dp값을 0처리나 에러 처리 가능.”

5. 복잡도 분석과 최적화

DP 문제에서 복잡도 분석은 면접관이 단골로 묻는 질문입니다. "이 DP 해법은 O(NM) 시간, O(NM) 메모리죠. 메모리 줄일 수 있나요?"라고 물을 때, "현재 dp는 2차원 배열이지만 이전 행만 참조하므로 O(M) 공간으로 줄일 수 있다"라고 대답하면 최적화 능력을 보일 수 있습니다.

또한 불필요한 메모리를 줄이거나 점화식을 약간 변형해 상수 공간이나 부분 최적화를 하겠다고 말해보세요. "이 DP는 이전 상태만 필요하므로 O(1) 공간으로 축소 가능합니다."라고 하면 면접관이 감탄할 수 있습니다.

6. 조건부 처리, 비동기 처리, 로깅, 에러 처리, Ranges 응용

조건부 처리:
예를 들어 문자열 DP 문제에서 문자열 길이가 너무 크면 메모리 초과 가능성을 생각해 dp 말고 다른 접근 고려할 수도 있습니다. 면접에서 이런 시나리오를 언급하면 문제 규모에 따른 솔루션 선택 능력을 보여줄 수 있습니다.

비동기 처리(Coroutine):
DP 테이블을 채우는 과정에서 매우 큰 데이터나 외부 I/O가 필요한 경우 coroutine으로 비동기 테이블 업데이트를 한다든가, streaming input에 대해 점진적으로 dp 값을 업데이트하는 상상을 해볼 수 있습니다. 면접관이 이런 상상을 긍정적으로 받아들일 수도 있습니다.

로깅(std::format):
DP 진행 과정에서 dp 배열 값을 각 단계마다 출력해 디버깅 가능. 면접 중 “개발 과정에서 dp 테이블 상태를 로깅해 잘못된 점화식이나 초기값 설정 실수를 잡아낼 수 있다”라고 말하면 코드 품질과 디버깅 능력을 강조할 수 있습니다.

에러 처리(std::expected):
dp 계산 중 잘못된 인덱스 접근이나 계산 불가능 시나리오(예: 문제가 조건상 불가능한 경우)에서 에러를 명시적으로 반환해 명확한 에러 처리를 할 수 있습니다.

Ranges 활용:
DP 결과 배열에 대해 Ranges를 사용해 특정 조건을 만족하는 dp 상태만 필터링하거나, dp 결과를 transform해 문제 후처리를 할 수도 있습니다. 예를 들어 dp 결과 배열에서 최댓값들을 뽑아내거나, 특정 인덱스 범위에 대한 부분 결과를 pipeline 형태로 처리 가능하다고 언급하면 모던 C++ 숙련도를 어필할 수 있어요.

7. 예제 문제로 실전 감각 키우기

• 피보나치 DP 예제:
  LeetCode "Fibonacci Number" 문제나 Baekjoon "피보나치 수 5" 문제로 dp 기초 연습.
• 최대 부분합 문제:
  LeetCode "Maximum Subarray" 문제로 dp를 통한 O(n)에 최대 부분합 계산 연습.
• 편집 거리(Edit Distance) 문제:
  LeetCode "Edit Distance" 문제로 O(NM) dp 테이블 채우기 연습. 문자열 dp 패턴 숙달.
• 격자 경로 DP 문제:
  Programmers "등굣길" 문제로 dp 테이블 채우는 전형적 문제. O(NM) 시간, 초기값 설정 주의.
• K나 M 등 파라미터 기반 DP 문제:
  백준에서 knapsack(배낭 문제), Codeforces 다양한 DP 문제로 상태 정의와 점화식 수립 훈련. 예: 0/1 knapsack에서 dp[i][w]=max(dp[i-1][w], dp[i-1][w-weight[i]]+value[i]) 식으로 점화식 세우는 연습.

각 문제를 풀 때 점화식 정의, 초기값 설정, 복잡도 분석, 코너 케이스 생각, 메모리 최적화(2D dp를 1D로 축소 등), 로깅/디버깅 전략, 면접 시 verbalize 방법을 정리해두면 실전에서 큰 도움이 됩니다.

8. 면접장에서의 사고 과정 표현 예시

"Knapsack 문제"를 받았다고 가정해볼게요. “N개 아이템이 있고, 각 아이템은 가치와 무게가 있으며, 배낭 용량 W 내에서 가치 합을 최대로 하라”는 전형적 DP 문제.

1. 접근 아이디어 언급: "이 문제는 중복되는 하위 문제가 많은 전형적 DP 문제입니다. dp[w]를 무게 w까지 고려했을 때 얻을 수 있는 최대 가치로 정의해봅시다."
2. 점화식 수립: "0/1 Knapsack에서는 dp[w]=max(dp[w], dp[w-weight[i]]+value[i]) 형태로 점화식을 세울 수 있습니다. 단, i번째 아이템을 선택할 수 있다면 w-weight[i] 상태에서 i번째 아이템을 추가해 dp[w]를 갱신할 수 있죠."
3. 초기값/복잡도: "dp[0]=0으로 시작, 모든 w에 대해 초기값은 0. O(N*W) 시간, O(W) 공간으로 구현 가능. n이 크면 이 방법이 느릴 수 있지만 n/W 범위나 아이템 특성을 고려해 더 최적화나 조건부 접근 시도 가능."
4. 코너 케이스: "빈 아이템 리스트면 dp[w]=0, W=0이면 항상 0. 아이템 무게가 W보다 큰 경우 그 아이템 건너뛰기 처리."
5. 면접 시 의사소통: "이 문제를 하위 문제로 나누면 무게 w에 대해 최대 가치 dp[w]를 정의할 수 있고, 아이템을 하나씩 보며 dp 값을 갱신하면 O(NW) 시간에 해결 가능합니다. 추가 메모리를 최소화하기 위해 1D dp 배열을 뒤에서부터 갱신하면 O(W) 공간으로 가능해요. 필요하다면 std::format으로 dp 배열 변화 과정을 로깅하거나, std::expected로 W<0같은 비정상 입력 시 에러 반환도 가능하죠."

이처럼 매우 상세히 언어화하면 면접관이 여러분의 로직 이해도와 커뮤니케이션 능력을 높게 평가할 것입니다.

마무리

이번 글에서는 동적 프로그래밍(DP) 문제에서 어떻게 점화식을 세우고, 탑다운/바텀업 접근 중 하나를 선택하며, 코너 케이스와 복잡도 최적화, 메모리 감소 방법을 고민하는지 매우 구체적이고 단계별로 다뤄보았습니다. 또한 다양한 예제(피보나치, 최대 부분합, 편집 거리, 격자 경로, knapsack)로 패턴을 익히고, 면접에서 이를 논리적으로 표현하는 방법을 제안했습니다.

이제 여러분은 DP 문제를 접했을 때 “이 문제를 어떤 상태 정의 dp[i] 또는 dp[i][j]로 할까?”, “점화식을 어떻게 세울까?”, “바텀업으로 O(NM)에 해결 가능할까?”, “메모리를 O(M)으로 줄일 수 있나?”, “코너 케이스는 어떻게 처리할까?” 같은 질문을 자연스럽게 던지고, 그에 대한 답을 단계별로 찾아나갈 수 있을 것입니다. 그리고 면접관에게 그 생각의 흐름을 명확히 verbalize하여 높은 평가를 받을 수 있겠죠.

이러한 DP 패턴의 내면화는 인터뷰뿐만 아니라 실제 코딩 작업에서도 큰 도움을 줄 것입니다. DP 문제는 어렵지만, 패턴을 체득하면 큰 무기가 될 수 있으니 꾸준히 문제를 풀며 감을 쌓아보세요.