C++ 코딩테스트 강좌, 동적 계획법 알아보기

1. 동적 계획법이란?

동적 계획법(Dynamic Programming, DP)은 복잡한 문제를 작은 부분 문제로 나누어 해결하고, 이미 계산한 결과를 저장하여 반복 계산을 방지하는 알고리즘 설계 기법입니다. 주로 최적화 문제에서 사용되며, 시간 복잡도를 줄이고 효율적인 해결책을 제공합니다.

1.1. 동적 계획법의 특징

  • 부분 문제 최적성: 문제를 해결하기 위해 필요한 모든 하위 문제의 최적해를 구해야 합니다.
  • 오버래핑 서브프레블럼: 동일한 하위 문제가 여러 번 계산되는 것을 방지합니다.

2. 문제 소개

문제: 최대 부분 수열 합

정수로 이루어진 배열에서 연속된 부분 수열의 합이 최대가 되는 값을 구하는 문제입니다. 예를 들어, 배열 {-2, 1, -3, 4, -1, 2, 1, -5, 4}의 최대 부분 수열 합은 6으로, 부분 수열 {4, -1, 2, 1}의 합입니다.

문제 입력

  • 첫 줄에 배열의 크기 N (1 ≤ N ≤ 100,000)이 주어진다.
  • 두 번째 줄에 배열의 원소가 공백으로 구분되어 주어진다.

문제 출력

최대 부분 수열 합을 출력한다.

3. 문제 해결 과정

3.1. 접근 방법

이 문제를 동적 계획법으로 해결하기 위해서는 다음과 같은 단계로 접근할 수 있습니다:

  1. 문제 정의: dp[i]를 i번째 원소까지의 최대 부분 수열 합으로 정의합니다.
  2. 점화식 세우기: 점화식은 dp[i] = max(arr[i], dp[i-1] + arr[i]) 입니다. 즉, i번째 원소를 포함할지 말지를 결정합니다.
  3. 초기값 설정: dp[0] = arr[0]로 시작합니다.
  4. 최댓값 계산: 모든 원소를 순회하면서 최대 값을 갱신합니다.

3.2. C++ 코드 구현


#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int N;
    cin >> N;
    vector arr(N);
    for(int i = 0; i < N; i++) {
        cin >> arr[i];
    }

    vector dp(N);
    dp[0] = arr[0];
    int maxSum = dp[0];

    for(int i = 1; i < N; i++) {
        dp[i] = max(arr[i], dp[i - 1] + arr[i]);
        maxSum = max(maxSum, dp[i]);
    }

    cout << maxSum << endl;

    return 0;
}

4. 코드 설명

위 코드에서는 먼저 배열의 크기 N과 배열 원소를 입력받습니다. 그 다음 dp 배열을 선언하여 각 인덱스까지의 최대 부분 수열 합을 저장합니다. 이후 반복문을 통해 dp 값을 갱신하고, 그 과정에서 최대 값을 찾습니다.

4.1. 시간 복잡도

이 알고리즘의 시간 복잡도는 O(N)입니다. 배열을 한 번 순회하기 때문에 선형 시간 복잡도를 가집니다.

4.2. 공간 복잡도

공간 복잡도 또한 O(N)이며, 최대 N개의 값을 저장합니다. 그러나, dp 배열을 사용하지 않고 두 변수로 최대 합을 구하는 방법도 있습니다.

5. 결론

동적 계획법은 복잡한 문제를 효율적으로 해결할 수 있는 강력한 기법입니다. 최대 부분 수열 합 문제는 동적 계획법의 기본 개념을 이해하는 데에 도움을 주며, 코딩테스트에서도 자주 등장하므로 충분한 연습이 필요합니다.

© 2023 C++ 코딩테스트 강좌