다이나믹 프로그래밍 핵심 정리

코딩테스트에 거의 항상 출제되는 다이나믹 프로그래밍(Dynamic Programming, DP)에 대해 정리해 보겠습니다.

DP의 기본 원리와 접근법

다이나믹 프로그래밍(Dynamic Programming, DP)은 처음 들으면 어려워 보이지만, 사실 중학교에서 배우는 수학적 귀납법과 비슷한 원리입니다.

수학적 귀납법

수학적 귀납법을 가볍게 복습해 봅시다. 어떤 주장이 모든 자연수에 대해 성립한다는 것을 증명할 때, 우리는 두 단계로 나눠 증명합니다:

기본 단계: 가장 작은 수(보통 1)에서 성립함을 보여줍니다.
귀납 단계: n에서 성립한다면, n+1에서도 성립한다는 것을 보여줍니다.

예를 들어, "1부터 n까지의 자연수 합은 n(n+1)/2이다"라는 공식을 증명할 때:

기본 단계: n=1일 때, 1 = 1(1+1)/2 = 1 (성립함)
귀납 단계: n=k일 때 성립한다고 가정하면, 1+2+...+k = k(k+1)/2
이제 n=k+1일 때도 성립하는지 확인: 1+2+...+k+(k+1) = k(k+1)/2 + (k+1) = (k+1)(k/2 + 1) = (k+1)(k+2)/2 (성립함)

이렇게 작은 문제(n=1)부터 시작해 큰 문제(n=자연수)를 해결하는 과정이 바로 DP와 같은 원리입니다

DP의 기본 원리

DP는 복잡한 문제를 작은 부분 문제로 나누고, 이 부분 문제들의 해답을 차례로 구해 최종 문제를 해결하는 방법입니다.

작은 문제부터 풀기: 수학적 귀납법처럼 가장 작은 문제(기본 단계)부터 시작합니다.
이전 결과 활용: 더 큰 문제를 풀 때 이미 풀었던 작은 문제의 결과를 활용합니다.
결과 저장하기: 한 번 푼 문제의 결과는 배열이나 표에 저장해 두고 다시 계산하지 않습니다.

예시: 계단 오르기

예를 들어, 계단을 오르는 방법의 수를 구하는 문제를 생각해 봅시다. 한 번에 1칸 또는 2칸씩 오를 수 있다면, n개의 계단을 오르는 방법은 몇 가지일까요?

1칸인 경우: 1가지 방법 (1칸 오르기)
2칸인 경우: 2가지 방법 (1칸+1칸 또는 2칸 한 번에)
3칸인 경우: 3가지 방법 (1+1+1 또는 1+2 또는 2+1)

n칸을 오르는 방법의 수는 (n-1) 칸을 오르는 방법의 수 + (n-2) 칸을 오르는 방법의 수와 같습니다. 이렇게 작은 문제의 결과를 이용해 큰 문제를 풀어나가는 것이 DP의 핵심입니다.

DP는 어려워 보이지만, "이전에 풀었던 문제의 답을 재활용하자"라는 아이디어에서 시작합니다. 수학적 귀납법처럼, 작은 경우부터 해결해 나가는 것이죠.

Top-down vs Bottom-up 구현

다이나믹 프로그래밍을 구현하는 방법에는 크게 두 가지가 있습니다: 위에서 아래로 접근하는 Top-down 방식과 아래에서 위로 쌓아 올리는 Bottom-up 방식입니다. 둘 다 같은 문제를 해결하지만, 접근 방법이 다릅니다.

Top-down 방식

Top-down 방식은 큰 문제부터 시작해서 작은 문제로 내려가는 방식입니다. 재귀적 접근을 사용하며, 이미 계산한 값은 메모리에 저장해 두고 재활용합니다. 이를 '메모이제이션(Memoization)'이라고 합니다.

예를 들어, 피보나치 수열을 계산할 때 Top-down 방식을 사용한다면

10번째 피보나치 수를 구하려면 먼저 9번째와 8번째를 알아야 합니다.
9번째를 구하려면 8번째와 7번째를 알아야 합니다.
이런 식으로 계속 작은 문제로 쪼개 내려갑니다.
1번째와 2번째 피보나치 수는 기본값으로 알고 있습니다(각각 1).
이미 계산했던 값(예: 8번째 피보나치 수)은 배열에 기록해 두고, 다시 필요할 때 재계산하지 않고 기록해 둔 값을 사용합니다.

Bottom-up 방식

Bottom-up 방식은 가장 작은 부분 문제부터 해결하고, 그 결과를 바탕으로 점점 큰 문제를 해결해 나가는 방식입니다. 테이블(배열)을 채워나가기 때문에 '타뷸레이션(Tabulation)'이라고도 합니다.

피보나치수열의 Bottom-up 구현을 예로 들면

1번째와 2번째 피보나치 수는 각각 1로 시작합니다(기본 값).
3번째 피보나치 수는 1번째와 2번째를 더해서 2입니다.
4번째는 2번째와 3번째를 더해서 3입니다.
이런 식으로 순서대로 계산해 나가며 10번째까지 합니다.
각 단계의 결과는 배열에 차례로 기록해 둡니다.

이 방식은 벽돌을 쌓듯이 기초부터 차근차근 결과를 쌓아 올립니다. 마치 1층부터 시작해 10층 건물을 짓는 것처럼, 1번째 피보나치 수, 2번째 피보나치 수... 이렇게 순서대로 구해나가는 방식입니다.

두 방식의 차이점

Top-down: 직관적이고 재귀적 사고에 익숙한 사람에게 이해하기 쉽습니다. 필요한 부분만 계산합니다. 마치 목적지부터 시작해서 출발점을 찾아가는 여행과 비슷합니다.
Bottom-up: 일반적으로 더 효율적이며 재귀 호출의 부담이 없습니다. 모든 부분 문제를 순서대로 계산합니다. 출발점에서 시작해 목적지까지 한 걸음씩 나아가는 여행과 비슷합니다.

두 방식은 상황에 따라 적절히 선택하면 됩니다. 어떤 문제는 Top-down이 더 자연스럽고, 어떤 문제는 Bottom-up이 더 효율적입니다.

자주 출제되는 DP 문제 유형

다이나믹 프로그래밍은 코딩 테스트에서 자주 출제되는 유형입니다. 아래에서는 가장 대표적인 DP 문제 유형들을 살펴보겠습니다.

1. 최적화 문제

최적화 문제는 가장 작은 값이나 가장 큰 값을 찾는 문제입니다. DP가 가장 많이 활용되는 유형이죠.

예시: 배낭 문제(Knapsack Problem)

문제 상황: 가방에 물건들을 넣어야 하는데, 가방은 무게 제한이 있습니다. 각 물건은 가치와 무게가 있을 때, 가방에 넣을 수 있는 물건들의 최대 가치를 구하는 문제입니다.
접근 방법: DP[i][w]를 "처음부터 i번째 물건까지 고려했을 때, 무게 w의 가방에 넣을 수 있는 최대 가치"로 정의합니다. 각 물건을 넣거나 넣지 않는 두 가지 선택지 중 더 큰 가치를 선택하면 됩니다.

2. 경우의 수 구하기

격자나 그래프에서 특정 조건을 만족하는 경우의 수를 구하는 문제입니다.

예시: 격자 경로 문제

문제 상황: N×M 격자에서 왼쪽 위에서 오른쪽 아래로 이동하려고 합니다. 오른쪽이나 아래쪽으로만 이동할 수 있다면, 가능한 경우의 수는 몇 개인가요?
접근 방법: DP[i][j]를 "왼쪽 위에서 (i,j) 위치까지 도달하는 경우의 수"로 정의합니다. 그러면 DP[i][j] = DP[i-1][j] + DP[i][j-1]이 됩니다.

3. 수열과 관련된 문제

수열에서 특정 조건을 만족하는 부분을 찾는 문제입니다.

예시: 최장 증가 부분 수열(LIS)

문제 상황: 수열이 주어졌을 때, 증가하는 부분 수열 중 가장 긴 것의 길이는? (수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4입니다.)
접근 방법: DP[i]를 "i번째 원소를 마지막으로 하는 최장 증가 부분 수열의 길이"로 정의합니다. 각 위치마다 이전 원소들을 확인해서 증가 조건을 만족하는 것 중 가장 긴 길이에 1을 더합니다.

위 유형들은 DP 문제의 대표적인 문제들입니다. 이 문제들도 쉬운 것은 아니지만 DP는 어렵게 내려면 정말 끝도 없이 어려워집니다. 그러니 다양한 유형들을 많이 풀어보는 것, 그리고 한 문제를 오랫동안 생각해 보는 것이 중요합니다. 기본 유형을 마스터하면 응용문제도 해결할 수 있는 감각이 생길 것입니다.

xylavo 님의 블로그