[C++로 배우는 알고리즘과 자료구조] Day 28: 동적 계획법 (DP) 기초

동적 계획법 (Dynamic Programming, DP)

동적 계획법(DP)은 복잡한 문제를 해결하기 위해 작은 부분 문제로 나누어 해결하고, 그 결과를 저장하여 전체 문제의 해를 구하는 알고리즘 설계 기법입니다. DP는 주로 재귀적 구조를 가지며, 중복되는 부분 문제를 해결하여 효율성을 높입니다.

DP의 주요 특징:

1. 중복된 부분 문제 (Overlapping Subproblems): 문제를 해결하는 과정에서 동일한 부분 문제가 여러 번 재계산됩니다.
2. 최적 부분 구조 (Optimal Substructure): 문제의 최적 해는 부분 문제의 최적 해로 구성될 수 있습니다.

DP의 접근 방식:

1. 탑다운 (Top-Down): 재귀 + 메모이제이션
2. 바텀업 (Bottom-Up): 반복문 + 테이블

피보나치 수열 (Fibonacci Sequence)

피보나치 수열은 동적 계획법을 이해하는 데 좋은 예제입니다. 피보나치 수열의 n번째 항은 다음과 같이 정의됩니다:

• ( F(n) = F(n-1) + F(n-2) )
• 초기 조건: ( F(0) = 0 ), ( F(1) = 1 )

탑다운 접근 방식 (Top-Down Approach)

탑다운 DP 구현 (재귀 + 메모이제이션)

#include <iostream>
#include <vector>

// 피보나치 수열 계산 함수 (탑다운 접근 방식)
int fibonacci(int n, std::vector<int>& memo) {
    if (n <= 1) {
        return n;
    }

    // 메모이제이션: 이미 계산된 값이 있으면 반환
    if (memo[n] != -1) {
        return memo[n];
    }

    // 값 계산 후 메모에 저장
    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
    return memo[n];
}

int main() {
    int n = 10;
    std::vector<int> memo(n + 1, -1); // 메모이제이션 벡터 초기화

    std::cout << "피보나치 수열의 " << n << "번째 항: " << fibonacci(n, memo) << std::endl;

    return 0;
}

바텀업 접근 방식 (Bottom-Up Approach)

바텀업 DP 구현 (반복문 + 테이블)

#include <iostream>
#include <vector>

// 피보나치 수열 계산 함수 (바텀업 접근 방식)
int fibonacci(int n) {
    if (n <= 1) {
        return n;
    }

    std::vector<int> fib(n + 1);
    fib[0] = 0;
    fib[1] = 1;

    for (int i = 2; i <= n; ++i) {
        fib[i] = fib[i - 1] + fib[i - 2];
    }

    return fib[n];
}

int main() {
    int n = 10;

    std::cout << "피보나치 수열의 " << n << "번째 항: " << fibonacci(n) << std::endl;

    return 0;
}

설명

1. 탑다운 접근 방식 (Top-Down Approach):
   • 재귀와 메모이제이션을 사용하여 문제를 해결합니다.
   • 재귀 호출을 통해 문제를 작은 부분 문제로 나누고, 계산된 결과를 메모이제이션 벡터에 저장하여 중복 계산을 방지합니다.
2. 바텀업 접근 방식 (Bottom-Up Approach):
   • 반복문과 테이블을 사용하여 문제를 해결합니다.
   • 작은 부분 문제부터 차례대로 해결하여 최종 문제의 해를 구합니다.
   • 재귀 호출 없이 반복문을 통해 중복 계산을 방지합니다.

동적 계획법의 기본 개념과 두 가지 주요 접근 방식인 탑다운과 바텀업을 이해했습니다. 다음 단계로 넘어가며, 더 복잡한 동적 계획법 문제와 다양한 알고리즘을 학습해보겠습니다.

질문이나 피드백이 있으면 언제든지 댓글로 남겨 주세요. 내일은 "Day 29: 분할 정복 기법"에 대해 학습하겠습니다.