📚 Dynamic Programming(DP)

---

📚 Dynamic Programming

---

📚 Dynamic Programming이란?

• 복잡한 문제를 풀 때, 작은 문제를 풀어가며 전체 문제를 해결하는 방법
• 이 방식으로 중복 계산을 피하고 문제를 더 효율적으로 해결할 수 있도록 도와준다.
• 주로 최적화 문제에서 사용된다.

---

💡 핵심 아이디어

• 분할 정복과 비슷하지만, 중복된 부분 문제를 해결할 때의 효율성에 초점이 됨
• 문제를 더 작은 하위 문제로 나누고, 각 하위 문제를 한번만 풀어 그 결과를 메모리에 저장한 후 재사용한다.

---

💡 DP의 두가지 중요한 요소

1. 중복된 부분 문제
   • 문제를 여러번 풀 때 동일한 하위 문제가 반복해서 등장할 때가 있다.
   • 예를 들어, 피보나치 수열에서 fib(5)를 계산할 때 fib(4)와 fib(3)을 반복적으로 계산해야 하므로 중복 계산이 발생한다. 이럴때 DP를 사용하여 한번만 계산하고계산을 저장해두고 재사용한다
2. 최적 부분 구조
   • 문제를 해결하기 위해서는 하위 문제의 최적 해결 방법 이 전체 문제의 최적 해결 방법으로 이어진다는 특성이 있어야한다.

---

🔑 DP의 주요 접근 방식

1. **탑다운(Top - Down) 방식(재귀 + 메모이제이션)**
   • 재귀를 사용하여 문제를 해결하고, 그 과정에서 계산한 값을 메모이제이션 을 통해 저장하여 중복계산을 피함
   • 메모이제이션은 계산된 값을 배열이나 해쉬맵에 저장하고, 동일한 하위 문제가 등장할 때 그 값을 바로 참조 하는 방식이다.

💻 탑다운 예시

#include <iostream>
#include <vector>

std::vector<int> memo(100, -1); // -1로 초기화, 벡터의 초기 초기화값은 -1 이다.

int fib(int n) {
    if (n <= 1) return n; // 1일 때 값은 당연히 1(1가지 방법)
    if (memo[n] != -1) return memo[n]; // 이미 계산된 값이 있으면 반환
    memo[n] = fib(n-1) + fib(n-2);    // 계산 후 저장, 재귀
    return memo[n];
}

int main() {
    std::cout << fib(10) << std::endl; // 55
    return 0;
}

1. 바텁 업(Bottom - up) 방식(반복문 + 테이블)
   • 문제를 작은 하위 문제부터 차근차근 풀어나가면서 그 결과를 테이블(배열, 리스트) 등에 저장해간다.
   • 반복문을 호출하므로 오버헤드가 없다 , 탑다운 방식은 오버플로우가 발생가능성이 있다.
   • 일반적으로 반복문을 사용하여 모든 하위 문제를 해결하고, 최종적으로 원하는 값을 테이블에서 찾아 반환한다.

💻 바텀 업 예시

int fib(int n) {
    std::vector<int> dp(n+1, 0);
    dp[1] = 1;
    for (int i = 2; i <= n; ++i) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}

---

🛠 Dynamic Programming의 사용 예시

1. 피보나치 수열
   • fib(n) = fib(n-1) + fib(n-2)로 정의되며, DP를 사용하면 중복 계산을 피할 수 있다.
2. 배낭 문제
   • 주어진 물건의 무게와 가치를 기준으로 제한된 무게 내에서 최대 가치를 구하는 문제, 각 물건을 포함하거나 포함하지 않는 경우를 고려하여 최적 해를 찾는다.
3. 최단 경로 문제
   • 그래프에서 두 점 사이의 최단 경로를 찾는 문제로, DP를 사용하여 여러 경로를 탐색하고 최단 경로를 계산한다.
4. 문자열 편집 거리
   • 두 문자열을 하나로 바꾸는 최소 작업 횟수를 찾는 문제로, 삽입, 삭제, 교체를 최소화하는 방법을 구한다.

---

📌 정리

장점

• 효율성 : 중복 계산을 피할 수 있기 때문에, 시간 복잡도가 크게 줄어든다.
• 문제 해결 능력 : 복잡한 문제를 작은 하위 문제로 나누어 해결할 수 있다.

단점

• 메모리 사용 : DP는 하위 문제 결과를 저장해야하므로 추가적인 메모리 필요
• 문제 구조가 적합해야 함 : 최적 부분 구조 + 중복된 부분 문제를 가지는 문제에만 유효

• c
• dynamic-programming
• algorithm