(알고리즘) Dynamic Programming (DP) 개념 정리

Dynamic Programming (DP) 개념 정리

---

1. Optimization Problem이란?

Optimization Problem은 가능한 해답 중에서 **가장 최적의 해(solution)**를 찾는 문제입니다.

• “최적”이란 일반적으로 최대값(Maximum) 또는 **최소값(Minimum)**을 의미합니다.
• 예시:
  • 가장 적은 비용으로 목적지에 도달하는 경로
  • 최대 수익을 내는 주식 거래 시점
  • 최소 동전 개수로 거스름돈 만들기

✅ 하나의 문제에 대해 하나 이상의 최적 해가 존재할 수도 있음.

---

2. Dynamic Programming(DP)이란?

Dynamic Programming은 최적화 문제를 효율적으로 해결하는 알고리즘 설계 기법입니다.

핵심 아이디어

• 큰 문제를 작은 하위 문제들로 나누고
• 작은 문제들의 정답을 이용해 큰 문제의 정답을 구성함
• 이때 같은 하위 문제가 반복해서 등장하는 경우, 중복 계산을 피하기 위해 결과를 저장하고 재사용

---

3. DP의 필수 조건

DP는 다음 두 조건을 만족할 때 사용할 수 있습니다:

✅ 1) Optimal Substructure (최적 부분 구조)

• 전체 문제의 최적해가 하위 문제의 최적해로 구성될 수 있음
• 즉, 문제를 쪼갠 다음, 부분 문제를 해결한 결과만으로 전체 문제의 최적해를 만들 수 있어야 함

예:

• 최단 경로 = 이전까지의 최단 경로 + 현재 선택

---

✅ 2) Overlapping Subproblems (겹치는 부분 문제)

• 재귀적으로 문제를 푸는 과정에서 같은 하위 문제가 반복적으로 나타남
• 이 중복된 계산을 메모이제이션(Memoization) 또는 **테이블(Tabulation)**을 이용해 방지

예:

• 피보나치 수열: f(n) = f(n-1) + f(n-2) 계산 시, f(n-2)는 여러 번 중복 호출됨

---

4. DP의 두 가지 접근 방식

📌 1. Top-Down Approach (재귀 + 메모이제이션)

• 재귀 함수를 사용하여 문제를 해결하되, 이미 계산한 결과는 저장하여 재사용
• 필요한 서브 문제만 계산하게 되어 불필요한 연산을 줄일 수 있음
• 메모이제이션: 이미 계산한 결과를 캐시에 저장하고 다음에 재사용

특징:

• 코드가 간결하고 이해하기 쉬움
• 그러나 깊은 재귀 호출로 인해 스택 오버플로우 위험이 있음

// 피보나치 Top-Down 예시
int[] dp = new int[n+1];

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

---

📌 2. Bottom-Up Approach (반복문 + 테이블 채우기)

• 작은 문제부터 차례로 해결하며, **배열 또는 표(table)**에 결과를 저장해 나감
• 모든 하위 문제를 계산해야 전체 문제의 해답에 도달하는 경우 적합
• 재귀 없이 반복문을 사용 → 메모리 사용도 명확하고 안정적

특징:

• 재귀 호출이 없기 때문에 스택 오버플로우 문제 없음
• 코드는 다소 복잡할 수 있으나 성능은 더 안정적

// 피보나치 Bottom-Up 예시
int[] dp = new int[n+1];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
    dp[i] = dp[i-1] + dp[i-2];
}

---

5. DP 설계 절차

1. 문제 정의
   • 문제의 입력/출력 조건을 정확히 이해하고, 최적해의 구조적 특징을 분석한다.
2. 재귀적 관계 도출
   • 큰 문제와 하위 문제 간의 관계를 수식 또는 코드로 표현한다.
   • 예: opt(i) = max(opt(i-1), opt(i-2) + value[i])
3. 메모이제이션 or 테이블 설계
   • 이미 계산된 결과를 저장할 배열/자료구조를 설계한다.
   • 크기와 초기값 설정이 중요
4. DP 방식 선택 및 구현
   • 재귀 호출이 자연스러우면 Top-Down
   • 안정성과 예측 가능한 계산이 중요하면 Bottom-Up
5. 최적해 도출 및 출력
   • 테이블이나 캐시에 저장된 최종 값을 사용해 결과 반환
   • (선택) 최적해를 추적(traceback) 하여 실제 선택 경로 등을 구할 수도 있음

---

6. 예시 문제들

 

문제 유형	예시
최단 경로	다익스트라, 플로이드
최대 수익	주식 매매 최대 이익
조합 최적화	배낭 문제 (Knapsack Problem)
문자열 문제	최장 공통 부분 수열 (LCS), 편집 거리 (Edit Distance)
계단 오르기	점화식 설계 연습용 문제

 

---

마무리 요약

• DP는 최적화 문제를 풀기 위한 대표적인 알고리즘 설계 기법이다.
• 조건은 최적 부분 구조와 겹치는 부분 문제.
• 구현 방식은 Top-Down(재귀 + 메모이제이션) vs Bottom-Up(반복 + 테이블) 두 가지.
• 재귀적 관계 설정과 점화식 구성이 핵심이다.