이 튜토리얼에서는 최소 K 간격 이상 떨어진 요소들로 구성되는 최대 합 부분 수열(maximum sum subsequence)을 찾는 프로그램을 C++로 구현하는 방법을 알아봅니다.
정수로 이루어진 배열과 값 K가 주어집니다. 우리의 목표는 선택한 모든 요소가 서로 최소 K개 이상의 거리(즉, 인덱스 차이가 K+1 이상)를 유지하면서 그 합이 최대가 되는 부분 수열을 찾는 것입니다.
동적 계획법을 활용한 접근 방식
이 문제는 동적 계획법(Dynamic Programming)을 사용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- MS[i]: 인덱스 i부터 배열의 끝까지 범위에서 얻을 수 있는 최대 합을 저장합니다.
- 배열의 마지막 요소부터 시작해 역방향으로 순회하며 값을 채워 나갑니다.
- 각 위치에서 두 가지 선택지를 비교합니다. 현재 요소
arr[i]를 선택하는 경우와 건너뛰는 경우입니다. arr[i]를 선택하면 간격 조건 때문에 다음에 선택할 수 있는 요소는 최소i + k + 1번째부터이므로, 후보 값은arr[i] + MS[i + k + 1]이 됩니다.arr[i]를 건너뛰면 단순히MS[i + 1]값을 그대로 가져옵니다.- 두 값 중 더 큰 값을
MS[i]에 저장하며, 최종 결과는MS[0]입니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
// 최대 합 부분 수열을 찾는 함수
int maxSum(int arr[], int N, int k) {
int MS[N];
MS[N - 1] = arr[N - 1];
for (int i = N - 2; i >= 0; i--) {
if (i + k + 1 >= N)
MS[i] = max(arr[i], MS[i + 1]);
else
MS[i] = max(arr[i] + MS[i + k + 1], MS[i + 1]);
}
return MS[0];
}
int main() {
int N = 10, k = 2;
int arr[] = { 50, 70, 40, 50, 90, 70, 60, 40, 70, 50 };
cout << maxSum(arr, N, k);
return 0;
}
출력 결과
230
결과 설명
k = 2일 때 선택된 요소들은 인덱스 차이가 최소 3 이상이어야 합니다. 위 예제에서는 인덱스 1의 70, 인덱스 4의 90, 인덱스 8의 70을 선택하면 70 + 90 + 70 = 230으로 최대 합을 얻을 수 있습니다.
시간 및 공간 복잡도
- 시간 복잡도: O(N) — 배열을 한 번만 순회하므로 매우 효율적입니다.
- 공간 복잡도: O(N) — DP 테이블 MS[]를 저장하기 위해 크기 N의 추가 배열이 필요합니다.