동적 계획법 입문

✅ 1. 동적 계획법(DP)이란?

동적 계획법(Dynamic Programming)은 큰 문제를 작은 문제로 나누고, 그 하위 문제들의 결과를 저장하여 반복 계산을 줄이는 문제 해결 패러다임이다.

• 재귀 + 메모이제이션 = 동적 계획법
• 특정한 알고리즘이 아니라, 최적화 기법이다.

🔁 왜 필요한가?

기존의 단순한 재귀(Naive Recursion)는 같은 하위 문제를 여러 번 계산해서 불필요한 연산이 많다. 이를 방지하기 위해 이미 계산한 결과를 저장(Memoization)해 두고 재활용함으로써 성능을 극적으로 개선할 수 있다.

---

🧩 2. 핵심 개념: 메모이제이션(Memoization)

💡 정의

• 이미 계산한 값을 캐시에 저장해서, 같은 문제를 다시 계산하지 않도록 하는 최적화 기법.

🧠 장점

• 속도를 빠르게 함
• 연산 중복 제거
• 메모리를 약간 더 사용하더라도 효율적인 시간 절약

⚠️ 유의사항

• 캐시를 위한 메모리 공간이 필요하므로, 메모리 사용량 증가 가능성 있음
• 그러나 살을 내주고 뼈를 취한다는 전략처럼, 충분히 가치 있는 비용이다

---

🧪 3. 실전 예제: 이항 계수 (Combination)

문제

• ( 45C6 ) 을 계산하라
• 예: 45개의 숫자 중 6개를 뽑는 경우의 수

---

🧾 [코드1] 단순 재귀 방식

int combination(int n, int r)
{
    if (r == 0 || n == r)
        return 1;

    return combination(n - 1, r - 1) + combination(n - 1, r);
}

🔍 코드 분석

• 기저 사례:
  • 아무 것도 안 뽑거나 전부 뽑는 경우 → 1
• 점화식:
  • ( C(n, r) = C(n-1, r-1) + C(n-1, r) )
• ⚠️ 단점:
  • 중복 호출이 너무 많아 시간 복잡도가 ( O(2^n) )

---

🧾 [코드2] 메모이제이션 적용한 DP 방식

int cache[50][50];

int combination(int n, int r)
{
    if (r == 0 || n == r)
        return 1;

    int& ret = cache[n][r];
    if (ret != -1)
        return ret;

    return ret = combination(n - 1, r - 1) + combination(n - 1, r);
}

🔍 코드 분석

• int& ret = cache[n][r]로 참조하여 값 저장/재사용
• 초기화는 memset(cache, -1, sizeof(cache))로 처리 (계산 여부 판별)
• 중복 호출 제거 → 실행 시간 획기적 감소

---

🧾 [코드3] 전체 흐름 (main)

int main()
{
    ::memset(cache, -1, sizeof(cache));

    __int64 start = GetTickCount64();

    int result = combination(45, 6);

    __int64 end = GetTickCount64();

    cout << end - start << " ms" << endl;
}

⏱ 실행 시간 비교

방식	실행 시간
단순 재귀	359ms 이상
메모이제이션	0ms ~ 매우 빠름

---

🧠 4. 동적 계획법 사용 조건

조건	설명
최적 부분 구조	전체 문제의 해가 하위 문제들의 해로 구성될 수 있어야 한다
중복되는 하위 문제	동일한 하위 문제가 여러 번 등장함
캐시 가능	계산된 값을 저장하고 재사용 가능해야 함

---

🔧 5. 동적 계획법 구현

1. 기저 사례 정의:

   • ( C(n, 0) = 1 ), ( C(n, n) = 1 )

2. 캐시 초기화:

   • 계산 여부 판단을 위해 -1로 초기화

3. 캐시 확인 후 계산:

   • 이미 계산한 값이면 즉시 반환
   • 아니라면 점화식 따라 계산 후 저장

---