동적 계획법(DP) 에 대해 알아보자

 

동적 계획법(Dynamic Programing)

동적 계획법은 복잡한 문제를 풀기 위한 알고리즘 설계 기법 중 하나로, 문제를 작은 하위 문제(subproblem)로 나누고, 이 하위 문제의 해를 재활용하여 전체 문제를 푸는 방법이다.

이러한 동적 계획법은 분할 정복(Divide & Conquer) 알고리즘과 매우 유사한데 큰 문제를 작은 하위 문제로 나눈다는 공통점이 있다. 차이점이라면 작은 하위 문제로 나눈때 독립된 하위 문제로 나눌것인지(분할 정복), 중복되는 하위 문제로 나눈것인지(동적 계획법)에 차이가 있다.

---

핵심 개념

동적 계획법의 중요한 개념은 다음과 같다.

1. 최적 부분 구조(Optimal Substructure)
   
   • 하위 문제의 해가 큰 문제의 해를 구할 수 있어야 한다
   • 예: 피보나치 수열 F(n)=F(n−1)+F(n−2)F(n) = F(n-1) + F(n-2)F(n)=F(n−1)+F(n−2)
2. 중복되는 부분 문제(Overlapping Subproblems)
   • 동일한 하위 문제가 여러 번 반복해서 계산되는 경우
   • 예: 재귀적으로 피보나치 수를 계산하면 F(3)F(3)F(3)이 여러 번 계산됨
3. 메모이제이션(Memoization) 또는 테이블화(Tabulation)
   • 메모이제이션: 이미 계산한 하위 문제의 결과를 저장하여 재사용(재귀 기반)
   • 테이블화: 하위 문제를 해결한 결과를 테이블에 채워 넣는 방식(반복문 기반)

---

동작 방식

동적 계획법 알고리즘의 기본 작동 원리이다.

1. 문제를 작은 하위 문제로 나누기
   문제를 하위 문제로 나눈 뒤, 이를 순차적으로 해결
2. 결과 저장
   이미 계산한 결과를 저장하여 중복 계산을 방지
3. 저장된 결과 활용
   저장된 하위 문제의 해를 조합하여 더 큰 문제를 해결

---

동적 계획법의 종류

1. 상향식(Bottom-Up, Tabulation)
   • 작은 문제부터 시작해서 점차 큰 문제를 해결
   • 반복문을 사용하며 테이블에 값을 채움
   • 예: 피보나치 수열을 반복문으로 구현
2. 하향식(Top-Down, Memoization)
   • 큰 문제에서 시작하여 작은 문제로 나눔(재귀)
   • 이미 계산된 값을 메모리에 저장
   • 예: 재귀적 피보나치 구현에서 메모이제이션 사용

---

동적 계획법 문제 예시 (C++로 작성)

 

동적 계획법의 가장 유명하고 교과서적인 예시는 당연 피보나치 수열이라고 할 수 있다.

피보나치 수열은 F0​=0, F1​=1, Fn+2​=Fn+1​+Fn  으로 n=2부터 Fn = Fn-2 + Fn-1의 형태를 띄고있어 동적 계획법 알고리즘을 가장 잘 설명할 수 있다. 백준 1003번 피보나치 수열이 그 예라고 할 수 있겠다.

https://www.acmicpc.net/problem/1003

 

재귀 방식

#include <iostream>
using namespace std;

int fibonacci(int n) {
    if (n <= 1) {
        return n;
    }
    return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
    int n;
    cout << "Enter a number: ";
    cin >> n;
    cout << "Fibonacci(" << n << ") = " << fibonacci(n) << endl;
    return 0;
}

 

간단하지만 비효율적이다.(실행시간 재앙이다) 큰 문제를 입력하고 하위 문제로 점차 쪼개서 해결하는 Top-Down방식이다.

 

메모이제이션 방식

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

vector<int> memo;

int fibonacci(int n) {
    if (n <= 1) {
        return n;
    }
    if (memo[n] != -1) { // 이미 계산된 값이면 반환
        return memo[n];
    }
    memo[n] = fibonacci(n - 1) + fibonacci(n - 2); // 계산 및 저장
    return memo[n];
}

int main() {
    int n;
    cout << "Enter a number: ";
    cin >> n;

    memo.resize(n + 1, -1); // 크기를 n+1로 설정하고 -1로 초기화
    cout << "Fibonacci(" << n << ") = " << fibonacci(n) << endl;
    return 0;
}

재귀 알고리즘과 비슷하지만 계산된 결과를 기억하기 때문에 중복 계산을 방지하여 좀더 효율적으로 작동한다.

얘도 마찬가지로 큰 문제를 입력하고 하위 문제로 점차 쪼개서 해결하는 Top-Down방식이다.

 

테이블화

#include <iostream>
using namespace std;

int fibonacci(int n) {
    if (n <= 1) {
        return n;
    }

    int prev = 0, curr = 1, next;
    for (int i = 2; i <= n; ++i) {
        next = prev + curr;
        prev = curr;
        curr = next;
    }
    return curr;
}

int main() {
    int n;
    cout << "Enter a number: ";
    cin >> n;
    cout << "Fibonacci(" << n << ") = " << fibonacci(n) << endl;
    return 0;
}

반복문을 통해 더욱 효율적으로 작동한다. 일반적으로 가장 메모리가 절약되는 방식이다.

하위 문제를 해결해나가면서 큰 문제를 해결하는 Bottom-Up방식이다.

---

마치며

오늘은 동적 계획법(DP) 문제를 알아보았다. 이 알고리즘은 코딩 테스트에 단골로 출제되는 문제로 대표적으로 피보나치 수열, 최장 공통 부분 수열(Longest Common Subsequence, LCS), 배낭 문제(Knapsack Problem), 최단 경로 문제(Dijkstra, Floyd-Warshall), 문자열 유사도(Edit Distance) 등등이 있다.

DP를 잘 활용하여 시간 복잡도를 효율적으로 줄일 수 있도록 해보자