최대 합 증가 부분 수열(MSIS) 구하기 | C++ 동적 계획법 완벽 가이드

이 튜토리얼에서는 최대 합 증가 부분 수열(Maximum Sum Increasing Subsequence, MSIS) 문제를 해결하는 프로그램을 다룹니다.

N개의 정수로 이루어진 배열이 주어졌을 때, 배열에서 원소들을 선택하여 선택한 원소들이 오름차순으로 정렬된 순서를 유지하면서 그 합이 최대가 되도록 만드는 것이 목표입니다.

동적 계획법(DP) 접근 방식

이 문제는 최장 증가 부분 수열(LIS)과 매우 유사한 구조를 가지며, 동적 계획법으로 효율적으로 해결할 수 있습니다.

핵심 아이디어는 다음과 같습니다.

• msis[i]는 인덱스 i에서 끝나는 증가 부분 수열 중 최대 합을 저장합니다.
• 초기값은 각 원소 자체(arr[i])로 설정합니다.
• i보다 앞에 있는 모든 j에 대해 arr[i] > arr[j]이고 msis[j] + arr[i]가 더 크다면 msis[i]를 갱신합니다.
• 마지막으로 모든 msis[i] 값 중 최댓값을 반환합니다.

C++ 코드 예제

#include <bits/stdc++.h>
using namespace std;

// 최대 합을 반환하는 함수
int maxSumIS(int arr[], int n) {
    int i, j, max = 0;
    int msis[n];

    // msis 배열을 각 원소 값으로 초기화
    for (i = 0; i < n; i++)
        msis[i] = arr[i];

    // 동적 계획법으로 최대 합 계산
    for (i = 1; i < n; i++)
        for (j = 0; j < i; j++)
            if (arr[i] > arr[j] &&
                msis[i] < msis[j] + arr[i])
                msis[i] = msis[j] + arr[i];

    // 전체 최댓값 찾기
    for (i = 0; i < n; i++)
        if (max < msis[i])
            max = msis[i];

    return max;
}

int main() {
    int arr[] = {1, 101, 2, 3, 100, 4, 5};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Sum of maximum sum increasing subsequence is " <<
        maxSumIS(arr, n) << endl;
    return 0;
}

실행 결과

Sum of maximum sum increasing subsequence is 106

위 예제에서 최적의 증가 부분 수열은 {1, 2, 3, 100}이며, 그 합은 106입니다.

시간 복잡도 분석

이 알고리즘은 두 개의 중첩 반복문을 사용하므로 시간 복잡도는 O(n²)입니다. 공간 복잡도는 dp 배열을 위해 O(n)이 필요합니다.