다이나믹 프로그래밍이란?

1. DP를 사용할 수 있는 2가지 조건

모든 문제에 DP를 적용할 수 있는 것은 아닙니다. 아래 두 가지 조건을 모두 만족할 때 DP를 사용할 수 있습니다.

1. 최적 부분 구조
   • 큰 문제의 최적해(정답)가 작은 문제들의 최적해들로 구성될 수 있는 구조를 말합니다.
2. 중복되는 부분 문제
   • 동일한 작은 문제들이 반복해서 나타나는 구조여야 합니다. 이 반복되는 계산을 저장해 두는 것이 DP의 핵심입니다.

2. DP의 핵심 접근 방식

DP를 구현하는 방법은 크게 두 가지로 나뉩니다. 두 방식의 차이를 이해하는 것이 중요합니다.

📌 메모이제이션

• 방식: 큰 문제를 해결하기 위해 위에서부터 아래로 내려가며, 재귀(Recursion) 함수를 호출하는 방식입니다.
• 핵심: 이미 계산한 값을 배열이나 객체에 저장(Memo)해 두었다가, 필요할 때 꺼내 씁니다.

📌 타뷸레이션

• 방식: 가장 작은 기본 문제부터 차례대로 정답을 구해 나가며 테이블을 채우는(Tabulation) 방식입니다.
• 핵심: 반복문(Loop)을 사용하며, 직관적이고 재귀 호출로 인한 스택 오버플로우 위험이 없어 실무 및 코딩 테스트에서 더 선호됩니다.

3. 핵심 문제 풀이: 피보나치 수열

DP를 이해하는 가장 좋은 예제인 피보나치 수열을 두 가지 방식으로 구현해 봅니다.

피보나치 점화식: ```text F(n) = F(n-1) + F(n-2)```

⭕ Top-Down (재귀 + 메모이제이션)

class TopDownFibonacci {
  // 계산된 결과를 저장할 메모리 공간 (객체 또는 배열)
  private memo: Record<number, number> = {};

  public getFib(n: number): number {
    // 기저 조건 (Base Case)
    if (n === 1 || n === 2) return 1;

    // 이미 계산한 적이 있다면 저장된 값을 즉시 반환 (재활용)
    if (this.memo[n] !== undefined) {
      return this.memo[n];
    }

    // 계산 후 메모에 저장
    this.memo[n] = this.getFib(n - 1) + this.getFib(n - 2);
    return this.memo[n];
  }
}

const tdFib = new TopDownFibonacci();
console.log(tdFib.getFib(50)); // 메모이제이션 덕분에 순식간에 계산 완료!

⭕ Bottom-Up (반복문 + 타뷸레이션)

function bottomUpFibonacci(n: number): number {
  if (n === 1 || n === 2) return 1;

  // 데이터를 저장할 DP 테이블 초기화
  const dp: number[] = new Array(n + 1).fill(0);
  
  // 초기 조건 설정
  dp[1] = 1;
  dp[2] = 1;

  // 작은 문제부터 차례대로 계산하며 테이블 채우기
  for (let i = 3; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }

  return dp[n];
}

console.log(bottomUpFibonacci(50)); // 반복문 기반이라 스택 오버플로우 염려 없음

4. DP 문제 풀이 3단계 전략

실전 문제를 만났을 때 당황하지 않고 DP로 접근하는 프로토콜입니다.

1. DP 문제인지 의심하기
   • 문제가 그리디나 완전 탐색(DFS/BFS)으로 풀기에는 시간 초과가 날 것 같고, 대규모 데이터의 최적값을 요구할 때 의심하세요.
   • "이전의 선택이 다음 선택에 영향을 주는가?"를 체크합니다.
2. 점화식 세우기 (가장 중요)
   • 문제를 쪼개서 상태를 나타낼 변수를 정하고, 이 변수들 간의 관계를 식으로 표현해야 합니다.
   • 예: dp[i] = i번째 계단에 오를 때의 최댓값
3. 가장 작은 문제(초기값) 정의하기
   • dp[0], dp[1] 등 가장 직관적으로 알 수 있는 기저 조건의 값을 명시하고 반복문을 돌립니다.

5. 요약