동적 프로그래밍(Dynamic Programming, DP)

최적 부분 구조와 중복 계산을 해결하는 알고리즘의 핵심 기법

#️⃣ 들어가며

"최댓값", "최솟값", "최단 경로" 등을 구하고자 할 때, 단순히 가능한 모든 경우를 시도하면 계산량이 기하급수적으로 증가한다. 이러한 문제들 중 전체 문제가 부분 문제들의 최적 해를 조합한 결과라는 특징을 갖고 있다면 중복 계산을 줄이고 효율적으로 상태를 저장하는 기법, 즉 동적 프로그래밍(Dynamic Programming, DP)을 통해 시간 복잡도를 획기적으로 줄일 수 있다.

 

---

 

1️⃣ 동적 프로그래밍(Dynamic Programming, DP)

📌 정의

동적 프로그래밍(Dynamic Programming, DP)은 큰 문제를 작은 문제로 나누고, 작은 문제의 정답을 저장해서 재활용함으로써 전체 문제의 정답을 효율적으로 구하는 알고리즘 기법이다. 일반적으로, 재귀적 풀이에서 중복되는 계산을 줄이기 위해 사용된다.

 

예를 들어, 피보나치 수열을 계산한다고 할 때, 단순 재귀로 풀 경우, 시간 복잡도는 $O(2^{n})$이 된다. 이 때, 피보나치 수열 계산 방식을 확인해 보면 이미 계산한 값을 또 다시 계산하는 것을 확인할 수 있다. 동적 프로그래밍은 하위 문제의 정답을 저장하고, 동일한 계산이 다시 필요한 경우 기존 값을 재사용해서 전체 계산량을 줄인다.

$$F(n) \ = \ F(n \ - \ 1) \ + \ F(n \ - \ 2)$$

피보나치 수열 함수 호출 트리

 

✅ 꼭 만족해야 할 두 가지 조건

동적 프로그래밍을 적용하기 위해선 반드시 두 가지 조건을 만족해야 한다.

1. 최적 부분 구조 (Optimal Substructure)
   • 어떤 문제를 더 작은 하위 문제로 나누었을 때, 그 하위 문제들의 최적 해를 조합하면 전체 문제의 최적 해가 되는 특성
   • Ex) 최단 경로 : $A \ \rightarrow \ B \ \rightarrow \ C$로 가는 경로가 최단 경로라면, $A \ \rightarrow \ B$와 $B \ \rightarrow \ C$ 역시 각 구간에서의 최단 경로여야 함
   • Ex) 피보나치 수열 : $F(n) \ = \ F(n \ - \ 1) \ + \ F(n \ - \ 2)$
2. 중복되는 부분 문제 (Overlapping Subproblems)
   • 큰 문제를 여러 방식으로 나누었을 때, 같은 하위 문제가 반복해서 등장하는 경우
   • Ex) 피보나치 수열 : $F(3)$은 $F(5)$, $F(6)$ 계산 도중 두 번 이상 호출됨.

 

---

 

2️⃣ 동적 프로그래밍 구현 방식

🔨 Top-down (재귀 + 메모이제이션)

문제를 재귀적으로 정의한 뒤, 중복된 계산을 방지하기 위해 결과를 배열에 저장해두는 방식이다. 일반적으로 구현이 간단하고 직관적이며, 처음 접하는 문제에 빠르게 접근할 수 있으나, 재귀 호출이 깊을 경우 스택 오버플로우의 위험이 있다. 중간에 필요 없는 분기를 건너뛸 수 있어서 상태 수가 적은 문제에 유리하다.

int fib(int n) 
{
    if (n <= 1) return n;
    if (dp[n] != -1) return dp[n];
    
    return dp[n] = fib(n - 1) + fib(n - 2);
}

 

🔨 Bottom-up (반복문 + 테이블)

가장 작은 문제부터 순서대로 해결해나가며, 테이블을 채워나가는 방식으로, 재귀 호출 없이 반복문만 사용하므로 스택 오버플로우 문제가 없다. 대부분의 경우 속도 면에서 더 안정적이고 빠르며, 모든 상태를 한 번씩 다 처리하는 데에 강점을 가진다. 또한 구현 시, 테이블을 통해 상태 전이 흐름을 한눈에 볼 수 있어 디버깅이 쉬운 편이다.

dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++)
{
    dp[i] = dp[i - 1] + dp[i - 2];
}

 

---

 

3️⃣ 추가 사항

❗ 자주 하는 실수

1. 점화식을 정확히 세우지 않고 구현부터 시작함 : dp[i]가 무엇을 의미하는지를 명확히 정의하지 않으면 잘못된 계산이 반복됨
2. 메모이제이션 배열 초기값 설정 실수 : -1과 0의 구분이 중요한 문제에서 오류가 발생할 수 있으니 초기화 후 덮어쓰기 여부 주의
3. Top-down과 Bottom-up을 혼용하여 상태 혼란 발생 : 두 방식은 시작점, 종료 조건, 테이블 정의 방식이 다르므로 섞일 경우 오류가 쉽게 발생
4. 필요 이상으로 넓은 상태 정의 : 사용하지 않는 dp 배열 구간까지 낭비하며 계산하면 시간과 메모리 낭비
5. 경계 조건 미고려 : 경계 조건 처리를 소홀히 할 경우 런타임 에러 또는 틀린 정답일 가능성이 높아진다.

 

✅ 실전 팁

1. 문장을 먼저 서보자 : dp[i]는 무슨 의미인지 문장으로 정의하면 설계가 쉬워진다.
2. 작인 입력부터 테스트 : 예제를 손으로 풀면서 점화식이 맞는지 검증
3. 중간 상태 출력 : 디버깅할 땐 dp 배열을 출력해서 테이블 흐름을 확인
4. 입력 크기 고려 : 필요한 최소한의 크기만큼 배열을 선언하고, 메모리를 절약할 수 있으면 공간 최적화도 고려