Dynamic Programming(동적 계획법)

아이디어

하나의 큰 문제를 여러 개의 작은 문제로 나누고 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용

장점

재귀는 동일한 문제를 여러번 반복해서 풀어야한다는 단점이 있는데 DP는 이전에 계산한 값을 사용할 수 있어 효율적임

DP를 사용하기 위한 조건

1. Overlapping Subproblems(겹치는 부분 문제)

부분문제가 반복되어 나타나지 않는다면 재사용이 불가능하여 부분문제가 중복되는 경우에 효율적

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

부분문제의 최적 결과값을 사용하여 전체 문제의 최적 결과를 낼 수 있는 경우를 의미

문제 풀이 과정

1. DP로 풀 수 있는 문제인지 확인(조건을 만족하는지)
2. 문제의 변수 파악(변수의 개수 파악)
3. 변수 간 관계식 만들기(점화식) ex. f(n) = f(n-1) + f(n-2) 피보나치수열
4. 메모하기
5. 기저 상태 파악하기
6. 구현
   1) Bottom-Up: 반복문 사용, 아래에서부터 계산을 수행하고 누적시켜서 큰 문제를 해결
   2) Top-Down: 재귀 사용, 결과값을 재귀를 통해 전이시켜서 재활용하는 방식

구현 예시(피보나치)

#include <iostream>
#include <vector>
using namespace std;

int fibonacci(int n) {
    vector<int> dp(n + 1, 0); // 다이나믹 프로그래밍을 위한 배열

    // 초기값 설정
    dp[0] = 0;
    dp[1] = 1;

    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2]; // 이전 값들을 활용하여 현재 값을 구함
    }

    return dp[n];
}

int main() {
    int n = 10; // 피보나치 수열의 n번째 항을 구함
    cout << "피보나치 수열의 " << n << "번째 항: " << fibonacci(n) << endl;

    return 0;
}

참고자료

DP