동적 계획법(Dynamic Programming, DP)

큰 문제를 작은 문제로 나누고, 중복되는 부분 문제의 결과를 저장하여 다시 사용함으로써 전체 문제를 효율적으로 해결하는 최적화 기법

• 이전에 계산한 값을 재활용하여 중복 연산을 피하고 시간 복잡도를 줄이는 데 초점이 맞춰짐
• 일반적으로 최적화 문제나 조합/경우의 수 문제에서 사용됨
• 재귀와 메모이제이션을 활용한 Top-down 방식과, 반복문과 테이블을 활용한 Bottom-up 방식이 있음
• 점화식(이전 값과의 관계)을 세우는 것이 핵심
• 메모이제이션에는 배열로 만들어진 자료구조 또는 딕셔너리로 만들어진 자료구조가 자주 사용됨
• 장점
  • 중복 연산을 제거하여 성능 향상
  • 다이나믹하게 상태 변화 추적 가능
  • 재귀 + 캐싱으로 로직 단순화 가능(Top-down)
  • 반복문 기반으로 빠르게 계산 가능(Bottom-up)
• 단점
  • 문제에 따라 점화식 도출이 어렵고 설계 난이도가 있음
  • 메모이제이션을 위한 추가 메모리 사용
  • 대규모 DP 테이블은 공간 복잡도 증가

⭐️ DP 문제 설계 순서

1. 문제를 작은 단위로 나눌 수 있는가?
   • 문제를 작은 하위 문제로 쪼갤 수 있어야 DP 적용 가능
   • 예: 전체 최대값 → 앞쪽까지의 최대값들로 나눌 수 있는가?
2. 중복되는 계산이 발생하는가?
   • 동일한 서브 문제를 여러 번 계산하게 된다면 DP 사용이 적합
   • 예: 피보나치 수열은 같은 계산을 여러 번 반복함
3. 현재 상태를 어떤 변수들로 정의할 수 있는가?
   • dp[i], dp[i][j]처럼 상태 표현식을 만들어야 함
   • 몇 번째 원소까지 고려했는지, 어떤 조건이 붙었는지 등을 변수화
4. 점화식은 어떻게 세울 수 있는가?
   • 현재 상태를 이전 상태들과의 관계로 표현
   • 예: dp[i] = dp[i-1] + dp[i-2]
5. 초기값은 무엇인가?
   • 반복을 시작할 기반 값(Base case)을 명확히 설정해야 함
   • 예: dp[0] = 0, dp[1] = 1
6. Top-down으로 풀지, Bottom-up으로 풀지 결정
   • 재귀 + 메모이제이션: 간결, 구현 쉬움 (Top-down)
   • 반복문 + 테이블: 빠르고 안전, 메모리 예측 쉬움 (Bottom-up)

진행 과정 (Bottom-up 기준)

1. 상태 정의 → 점화식 도출
2. 초기값 설정
3. 반복문으로 작은 문제부터 해결
4. dp 테이블에 결과 저장
5. 최종 결과 추출

구현 코드(피보나치 수열)

자주 사용되는 ADT

자료구조	설명	활용 예
배열	상태를 인덱스로 표현, 테이블 저장용	피보나치, LIS 등
딕셔너리	동적 상태나 범위가 클 때	Top-down 방식에서 메모이제이션
2차원 배열	두 상태 이상 조합	LCS, 격자 DP 문제
큐	BFS + DP 조합 문제	최단 거리, 그래프 경로 등
스택	반복 재귀 시뮬레이션	DFS 기반 DP 문제 등

1. Top-down 방식 (재귀 + 메모이제이션)

• 중복 호출을 피하기 위해 memo라는 딕셔너리로 만들어진 자료구조를 사용

const fib = (n, memo = {}) => {
  if (n <= 1) return n;
  if (!memo[n]) {
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
  }
  return memo[n];
};

console.log(fib(10)); // 55

2. Bottom-up 방식 (반복문 + 테이블)

• dp는 배열로 만들어진 자료구조

const fib = (n) => {
  if (n <= 1) return n;
  const dp = [0, 1]; // 초기값 설정
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
};

console.log(fib(10)); // 55

시각화 예시 (Bottom-up)

i	0	1	2	3	4	5	6	7	8	9	10
dp[i]	0	1	1	2	3	5	8	13	21	34	55

시간 복잡도 및 공간 복잡도

• 시간 복잡도
  • Top-down: O(n)
  • Bottom-up: O(n)
• 공간 복잡도
  • O(n): 메모이제이션 테이블 사용 시
  • O(1): 최적화할 경우 (피보나치처럼 두 개의 값만 저장)

대표 문제 유형 및 핵심

문제	키워드	상태 표현식	점화식 형태
피보나치	단순 수열	dp[i]	dp[i-1] + dp[i-2]
계단 오르기	경우의 수	dp[i]	dp[i-1] + dp[i-2]
도둑질	최대합 + 조건	dp[i]	max(dp[i-1], dp[i-2] + val)
타일 채우기	조합	dp[i]	dp[i-1] + dp[i-2]
LIS	최대 길이	dp[i]	max(dp[j] + 1) if arr[j] < arr[i]
LCS	공통 부분 수열	dp[i][j]	같으면 +1, 다르면 max(좌, 상)
배낭 문제	선택 조합	dp[i][w]	max(선택X, 선택O)
최소 경로	최소 비용	dp[i][j]	min(좌, 상) + 현재 비용
동전 교환	최소 동전 수	dp[i]	min(dp[i], dp[i - coin] + 1)