Dynamic Programming

1. 동적 계획법의 개념 및 분할정복과의 차이

분할정복:

부분문제 간 상관관계가 없는 경우에 효과적.

(예: mergesort, quicksort)
피보나치 수열 등:

부분문제 결과가 여러 번 재사용됨(중복 계산 발생), 분할정복 비효율적

2. 피보나치 수열 계산

2.1 분할정복식(비효율)

cpp
CopyEdit
int fib(int n) {
  if (n <= 1) return n;
  else return fib(n-1) + fib(n-2);
}

중복 계산 존재, 시간복잡도 O(2ⁿ)

2.2 메모이제이션(memoization, top-down)

cpp
CopyEdit
int memo[MAX]; // memo[i] = -1로 초기화
int fib(int n) {
  if (n <= 1) return n;
  if (memo[n] == -1)
    memo[n] = fib(n-1) + fib(n-2);
  return memo[n];
}

중복 계산 제거, 각 값을 한 번만 계산

2.3 테이블 채우기(tabulation, bottom-up)

cpp
CopyEdit
int fib(int n) {
  int dp[0..n];
  dp[0] = 0; dp[1] = 1;
  for (int i = 2; i <= n; i++)
    dp[i] = dp[i-1] + dp[i-2];
  return dp[n];
}

작은 문제부터 큰 문제로 계산, 반복문 기반

3. Memoization vs Tabulation

	Memoization	Tabulation
방식	Top-down (재귀)	Bottom-up (반복)
계산	큰 문제 → 작은 문제	작은 문제 → 큰 문제
저장	캐시에 필요할 때 저장	모든 값을 테이블에 저장
장점	코드 직관적, 구현 쉬움	실행 빠름, 메모리 절약
단점	재귀 오버헤드 있음	전체 문제를 다 계산함

1. 동적 계획법의 개념 및 분할정복과의 차이

2. 피보나치 수열 계산

2.1 분할정복식(비효율)

2.2 메모이제이션(memoization, top-down)

2.3 테이블 채우기(tabulation, bottom-up)

3. Memoization vs Tabulation

4. 이항계수(Binomial Coefficient) 계산

4.1 재귀 관계식