이번 포스팅에서는 코딩테스트를 풀다 보면 접하게 될 "동적 프로그래밍"이라는 알고리즘 기법에 대해 정리하고 넘어가보려한다.

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

복잡한 문제를 더 작은 하위 문제로 나누고, 그 하위 문제들의 결과들을 저장하여 동일한 계산을 반복하지 않도록 하는 알고리즘 설계 기법

• 일반적으로 최적화 문제에서 많이 사용되며 특히 재귀적인 구조를 가진 문제에 효과적이다.
• DP는 두 가지 주요 개념인 메모이제이션(Memoization)과 하향식/상향식 접근 방식을 통해 성능을 최적화한다.

1. 메모이제이션(Memoization)

하위 문제의 결과를 저장하여, 동일한 하위 문제를 다시 계산할 필요가 없도록 하는 기법.
↪ 이를 통해 시간 복잡도를 줄이고, 성능을 크게 향상시킬 수 있다.

2. 하향식(Top-Down)과 상향식(Bottom-Up) 접근

1. 하향식(Top-Down) 방식

• 큰 문제를 작은 문제로 점점 쪼개가며 재귀 호출을 통해 해결하는 방법
• 하위 문제를 해결할 때 결과를 저장해 두고, 이후에 동일한 문제가 발생하면 저장된 결과를 재사용한다.

2. 상향식(Bottom-Up) 방식

• 작은 하위 문제를 먼저 해결하고, 그 결과를 이용해 큰 문제를 해결하는 방식
• 반복문을 사용하여 하위 문제부터 순차적으로 해결해나가며, 메모이제이션을 통해 효율적으로 문제를 풀 수 있다.

---

DP의 특징과 조건

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

문제의 최적 해가 하위 문제의 최적 해로부터 결정될 수 있어야 한다.

2. 중복되는 하위 문제(Overlapping Subproblems)

동일한 하위 문제가 여러 번 반복해서 등장해야 한다.

---

예시: 피보나치 수열

• 피보나치 수열의 n번째 항을 구하는 함수는 f(n) = f(n-1) + f(n-2)로 정의되며 n이 커질수록 계산해야 할 값이 급격히 증가한다.
• DP를 사용하여 이미 계산된 값을 저장해두면 중복된 계산을 피할 수 있다.

하향식(Top-Down) (메모이제이션 사용)

function fibonacci(n, memo = {}) {
  if (n <= 1) return n;
  if (memo[n]) return memo[n];  // 이미 계산된 값이 있으면 바로 반환
  memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
  return memo[n];
}

상향식(Bottom-Up)

function fibonacci(n) {
  if (n <= 1) return n;
  let fib = [0, 1];
  for (let i = 2; i <= n; i++) {
    fib[i] = fib[i - 1] + fib[i - 2];
  }
  return fib[n];
}

---

• 동적 프로그래밍은 피보나치 수열뿐만 아니라 아래의 문제들을 포함한 다양한 문제에 활용된다.
  • 최단 경로 문제
  • 배낭 문제(Knapsack Problem)
  • 문자열 관련 문제(ex. 최소 편집 거리)

---

DP 장단점

장점

• 중복 계산을 줄여 시간 복잡도를 낮출 수 있다.
• 최적화 문제를 효율적으로 해결할 수 있다.

단점

• 메모리 사용량이 많아질 수 있다.
• 문제에 따라 적용이 제한적일 수 있다.
• 초기 설계와 구현이 복잡할 수 있다.