[C++] Dynamic Programming (동적 계획법) 정리

Dynamic Programming (동적 계획법)

복잡한 문제를 간단한 문제(sub-problems)로 쪼개어 해결하는 알고리즘

---

❓ 피보나치 수열 문제 예시

 

DP table를 사용하기 위해서는 다음 두 가지 조건을 만족해야 한다.

 

1. Optimal Structure (최적 부분 구조)

1-a. 해당 문제를 작은 문제로 분할할 수 있어야 한다.

 F(5)를 구하기 위해서는 F(4)와 F(3)을 계산해야 한다. 따라서 F(5) 문제를 F(4)와 F(3)이라는 작은 문제로 나누어 해결할 수 있다.

1-b. 작은 문제의 해결 방법을 통해 큰 문제의 해결 방법을 구할 수 있어야 한다.

 피보나치 수열에서 n번째 항을 계산하기 위해서는 (n-1)번째 항과 (n-2)번째 항의 합을 계산해야 한다. 예를 들어, n=6인 경우를 생각해보면 다음과 같다.

F(6) = F(5) + F(4)
F(5) = F(4) + F(3)
F(4) = F(3) + F(2)
F(3) = F(2) + F(1)

 위와 같이 작은 문제의 해결 방법을 이용하여 F(6)을 구할 수 있다.

 

2. Overlapping Sub-problems (중복되는 문제)

작은 문제들이 반복해서 해결되는 방식을 거친다.

 F(4)를 구하기 위해서는 F(3)과 F(2)를 계산해야 한다.

 이 때, F(3)은 F(2)와 F(1)을 계산하기 위해 이미 사용되었다. 따라서, F(3)을 한 번 계산해두면, 이를 재사용하여 F(4)를 계산할 수 있다.

 이와 같은 방식으로, 이전에 계산한 결과를 저장해두고 재사용함으로써, 계산 속도를 빠르게 할 수 있다.
작은 문제들이 반복해서 해결되는 방식을 거친다.

 

 

 

---

Dynamic Programming의 구체적인 방식

6번째 피보나치 수를 구하는 코드를 비교해보자

 

0. 피보나치 코드의 재귀 함수를 이용한 구현

#include <iostream>
using namespace std;

int fibonacci(int n) {
    if (n <= 1) {
        return n;  // n이 1 이하인 경우, n을 반환
    }
		// n이 2보다 크면, 재귀적으로 호출하여 피보나치 수열을 계산
    return fibonacci(n-1) + fibonacci(n-2);
}

int main() {
    int n = 6;
    cout << fibonacci(n) << endl;
    return 0;
}

 

---

1. Top-down 방식 (재귀적 구현)

작은 부분 문제로 분할한 후, 재귀적으로 부분 문제를 해결하는 방법

결과를 메모이제이션하여 중복 계산을 피한다.

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

// n 값에 6을 넣으면, 6까지의 값이 계산됨.
// 계산된 값이 memo에 저장된 후 값을 return

int fibonacci(int n, unordered_map<int, int>&memo) {
    // memo 딕셔너리 안에 n이라는 key가 존재하는 경우,
		// 해당 값을 반환
		if (memo.find(n) != memo.end()) {
        return memo[n];
    }

		// n이 1 이하인 경우
		// n을 반환
    if (n <= 1) {
        return n;
    }

		// n-1과 n-2의 합을 memo[n]에 저장 후 memo[n]을 return
    memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo);

    return memo[n];
}

int main() {
    int n = 6;
    unordered_map<int, int> memo;
    cout << fibonacci(n, memo) << endl;
    return 0;
}

 

---

2. Bottom-up 방식 (반복적 구현)

작은 부분 문제부터 시작하여, 큰 문제를 해결해 나가는 방법

이러한 방법을 Tabulation이라고 함

#include <iostream>
using namespace std;

int memo[10];   // DP Table인 memo 배열 생성.

int fibonacci(int n) {

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

    for (int i = 2; i <= n; i++) {
        // 작은 문제부터 시작하여 이전에 계산한 결과를 이용하여 큰 문제 해결
        memo[i] = memo[i - 1] + memo[i - 2];
    }
    return memo[n];   // n번째 피보나치 수열 값 반환
}

int main() {
    int n = 6;   // n을 6으로 지정
    cout << fibonacci(n) << endl;   // fibonacci 함수를 호출하고, 결과를 출력
    return 0;
}

 

기본적으로 DP Table이라는 배열을 사용함.

• 인덱스 : 문제의 크기를 의미
• 값 : 해당 문제의 해답을 의미

 

---

Top-down(Memoization) vs Bottom-up(Tabulation)

 

1. 구현 방식
   • Memoization : 재귀 함수와 메모이제이션 배열을 사용하여 구현
   • Tabulation : 반복문과 배열을 사용하여 구현

 

1. 계산 방식
   • Memoization : 필요한 부분 문제만 계산
   • Tabulation : 모든 부분 문제를 계산

 

1. 메모리 사용
   • Memoization : 배열의 크기를 미리 지정하지 않아도 되므로 메모리 사용량을 줄일 수 있음
   • Tabulation : 배열의 크기를 미리 지정해야 하므로 더 많은 메모리를 사용할 수 있음

 

1. 오버헤드 (프로그램 실행 과정에서 추가적으로 발생하는 비용)
   • Memoization : 재귀 함수를 사용하기 때문에 함수 호출 오버헤드가 있을 수 있음
   • Tabulation : 반복문을 사용하기 때문에 오버헤드가 없음

 

---

 

동적 계획법(Dynamic Programming) vs 분할 정복 (Divide and Conquer)

 

공통점

1. 모두 최적화 문제를 해결하는 데 사용되는 방법론
2. 원래 문제를 부분 문제로 나누어 해결

 

차이점

1. 동적 계획법
   • 중복 계산을 피하기 위해 이미 계산한 결과를 저장하여 재활용
   • 메모리를 추가로 만들어 사용 → 중복 계산을 피하는 대신 시간 복잡도가 개선
   • 하향식(Top-down)과 상향식(Bottom-up) 두 가지 방식으로 구현

 

1. 분할 정복
   • 중복되지 않도록 각각의 부분 문제를 서로 겹치지 않게 나누어 해결
   • 재귀 호출을 사용 → 메모리를 상대적으로 적게 사용하지만, 시간 복잡도가 높은 문제를 해결하는 데 적합
   • 부분 문제들을 동시에 해결