다이나믹 프로그래밍(DP)의 기초와 핵심 전략

다이나믹 프로그래밍(Dynamic Programming, 동적 계획법)이란? 큰 문제를 작은 문제로 나누어 푸는 하향식/상향식 알고리즘 설계 기법입니다. 핵심은 **"한 번 계산한 작은 문제의 정답을 메모리에 저장(재활용)하여, 다시는 똑같은 계산을 하지 않도록 만드는 것"**입니다. (속도 향상의 치트키!)

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

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

최적 부분 구조 (Optimal Substructure)
중복되는 부분 문제 (Overlapping Subproblem)

2. DP의 핵심 접근 방식 2가지

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

📌 Top-Down (하향식) - 메모이제이션(Memoization)

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

📌 Bottom-Up (상향식) - 타뷸레이션(Tabulation) (★ 추천)

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

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

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

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

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

TYPESCRIPT

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 (반복문 + 타뷸레이션)

TYPESCRIPT

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로 접근하는 프로토콜입니다.

DP 문제인지 의심하기
점화식 세우기 (가장 중요)
가장 작은 문제(초기값) 정의하기

5. 요약

비교 항목	Top-Down (메모이제이션)	Bottom-Up (타뷸레이션)
주요 도구	재귀 함수 (Recursion)	반복문 (For loop)
가독성	점화식 형태를 그대로 코드로 옮기기 쉬움	흐름을 한눈에 파악하려면 숙련도가 필요함
장점	꼭 필요한 서브 문제만 계산함 (Lazy-evaluation)	스택 오버플로우가 없고 속도가 상대적으로 빠름
단점	재귀 깊이가 깊어지면 에러 발생 위험 있음	필요 없는 하위 문제까지 전부 계산될 수 있음

6. 마치며 느낀 점

무차별 대입(Brute Force)에서 탈출하기 그동안 코딩 테스트 문제를 풀 때 시간 초과가 나면 막막하기만 했는데, DP를 배우고 나니 "컴퓨터의 메모리를 활용해 시간을 번다"는 개념이 정립되었습니다. 기억력이 나쁜 프로그램에게 기록을 쥐여주는 것만으로 연산 속도가 기하급수적으로 빨라지는 게 흥미로웠습니다.

다이나믹 프로그래밍(DP)의 기초와 핵심 문제 풀이 전략