2 conditions for Dynamic Programming

1. 중복되는 부분 문제 (Overlapping Subproblems)

✅ 개념

• 문제를 해결하는 과정에서 동일한 부분 문제가 반복적으로 등장해야 합니다.
• 이전에 계산한 값을 저장하여 재사용하면 연산을 줄일 수 있어야 합니다.

🔹 예제: 피보나치 수열 (Fibonacci Sequence)

피보나치 수열을 재귀적으로 구하는 코드를 보면, 같은 값이 반복적으로 계산됩니다.

public static int fib(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fib(n - 1) + fib(n - 2);
}

❌ fib(5)를 구할 때 fib(3)이 두 번 계산됨.
❌ fib(3)을 계산할 때 fib(2)도 중복 계산됨.
✅ 중복된 계산을 저장하여 다시 계산하지 않으면 불필요한 연산이 많아짐.

📌 해결 방법: 메모이제이션 (Memoization)

중복 계산을 방지하기 위해, 한 번 계산한 값을 저장해 두고 다음에 필요할 때 바로 가져옵니다.

private static int[] memo = new int[100];

public static int fibMemo(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    if (memo[n] != 0) return memo[n]; // 이미 계산된 값 반환

    memo[n] = fibMemo(n - 1) + fibMemo(n - 2);
    return memo[n];
}

✅ 이렇게 하면 각 값이 한 번만 계산되므로 연산이 대폭 감소합니다.
✅ 즉, 중복되는 부분 문제를 저장해서 재사용하는 것이 핵심입니다.

---

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

✅ 개념

• 부분 문제의 최적해를 조합하여 전체 문제의 최적해를 구할 수 있어야 합니다.
• 즉, 부분 문제를 최적으로 해결하면 전체 문제도 최적이 되어야 합니다.

🔹 예제: 최단 경로 문제 (Dijkstra Algorithm)

A → D까지 가는 최소 비용 경로를 찾는다고 가정하겠습니다.

그래프 예시

   A --(10)--> B --(15)--> D
   A --(30)--> C --(20)--> D

가능한 경로

1. A → C → D (30 + 20 = 50)
2. A → B → D (10 + 15 = 25) ✅ 최적 경로

✅ 최단 경로(A → D) 는 최단 경로(A → B) + 최단 경로(B → D) 로 구할 수 있습니다.
✅ 부분 문제(A → B, B → D)의 최적해를 조합하면 전체 문제(A → D)의 최적해가 됩니다.
🔹 이런 성질을 "최적 부분 구조(Optimal Substructure)"라고 합니다.

❌ 최적 부분 구조가 없는 경우

어떤 문제들은 부분 문제의 최적해를 조합해도 전체 문제의 최적해가 되지 않습니다.

예제: 최장 경로 문제

최장 경로를 구할 때, 부분 문제의 최적해가 전체 문제의 최적해를 보장하지 않는 경우가 있습니다.

부분 문제(A → C, C → D)를 최적으로 해결해도, 전체 최적해(A → D)가 되지 않을 수 있음.
즉, 최적 부분 구조를 만족하지 않음 → DP 적용 불가능.

---

3. 동적 프로그래밍을 사용할 수 있는 문제 vs. 사용할 수 없는 문제

조건 동적 프로그래밍 적용 가능 동적 프로그래밍 적용 불가능

중복되는 부분 문제	피보나치 수열, 배낭 문제, LCS 문제	머지 정렬 (Merge Sort)
최적 부분 구조	최단 경로 문제, 동전 거스름돈 문제	최장 경로 문제

📌 중복되는 부분 문제 + 최적 부분 구조 → 동적 프로그래밍을 적용할 수 있음.
📌 하나라도 충족하지 않으면 DP 적용 불가능.

---

4. 결론

✅ 동적 프로그래밍을 적용하려면 두 가지 조건을 만족해야 한다.

1. 중복되는 부분 문제 → 이전에 계산한 값을 저장하여 재사용 가능해야 함.
2. 최적 부분 구조 → 부분 문제의 최적해를 조합하면 전체 문제의 최적해가 되어야 함.

📌 예제

• 적용 가능 → 피보나치 수열, 최단 경로 문제, 배낭 문제
• 적용 불가능 → 병합 정렬(Merge Sort), 최장 경로 문제