C++에서 주어진 합 이하의 최대 합을 가지는 부분 배열 찾는 방법

문제 개요

이 문제에서는 하나의 배열과 목표 합(sum)이 주어집니다. 우리가 해야 할 작업은 C++ 프로그램을 작성하여 주어진 합보다 작거나 같은 합을 가지는 부분 배열(subarray) 중 최대 합을 구하는 것입니다.

즉, 길이가 n 이하인 임의의 부분 배열 중에서 그 합이 주어진 값 이하가 되는 경우를 모두 고려해, 그중 가장 큰 합을 찾아야 합니다.

예제로 문제 이해하기

입력 − array = {3, 5, 1, 8, 2, 9}, sum = 25

출력 − 25

설명 − 합이 25 이하인 부분 배열 중 {5, 1, 8, 2, 9}의 합이 정확히 25로 가장 큽니다.

단순한 접근 방법과 한계

가장 간단한 방법은 배열을 반복적으로 순회하면서 가능한 모든 부분 배열의 합을 계산하고, 그중 주어진 합에 가장 가깝거나 같은 값을 찾는 것입니다. 하지만 이 방법은 두 개의 중첩 루프가 필요하기 때문에 시간 복잡도가 O(n²)으로, 배열의 크기가 커지면 비효율적입니다.

효율적인 해결 방법: 슬라이딩 윈도우(Sliding Window)

더 효율적으로 문제를 해결하려면 슬라이딩 윈도우 기법을 사용할 수 있습니다. 이 방법은 현재 윈도우(부분 배열)의 합을 최대 합과 지속적으로 비교하면서, 조건에 따라 윈도우에 요소를 추가하거나 제거하는 방식으로 동작합니다.

동작 과정을 요약하면 다음과 같습니다.

1. 왼쪽 포인터(start)와 오른쪽 포인터(i) 사이의 구간 합을 유지합니다.
2. 현재 합이 maxSum 이하이면 전체 최댓값(overallMax)을 갱신합니다.
3. 다음 요소를 더했을 때 maxSum을 초과하면, 초과하지 않을 때까지 왼쪽 요소들을 제거합니다.
4. 이 과정을 배열 끝까지 반복합니다.

이 기법을 사용하면 시간 복잡도를 O(n)으로 줄일 수 있습니다.

구현 예제

아래는 위 해결 방법의 동작을 보여주는 C++ 프로그램입니다.

#include <iostream>
using namespace std;
int findMax(int a, int b){
   if(a>b)
      return a;
   return b;
}
int maxSumsubarray(int arr[], int n, int maxSum){
   int sum = arr[0], overallMax = 0, start = 0;
   for (int i = 1; i < n; i++) {
      if (sum <= maxSum)
      overallMax = findMax(overallMax, sum);
      while (sum + arr[i] > maxSum && start < i) {
         sum -= arr[start];
         start++;
      }
      sum += arr[i];
   }
   if (sum <= maxSum)
      overallMax = findMax(overallMax, sum);
   return overallMax;
}
int main(){
   int arr[] = {3, 1, 4, 7, 2, 9, 5};
   int n = sizeof(arr) / sizeof(arr[0]);
   int sum = 20;
   cout<<"The maximum sum of subarray with sum less than or equal to "<<sum<<" is "<<maxSumsubarray(arr, n, sum);
   return 0;
}

실행 결과

The maximum sum of subarray with sum less than or equal to 20 is 18

정리

배열 {3, 1, 4, 7, 2, 9, 5}에서 합이 20 이하인 부분 배열 중 최대 합은 18({3, 1, 4, 7, 2} 또는 {4, 7, 2, 5} 등)입니다. 슬라이딩 윈도우 기법을 활용하면 모든 부분 배열을 일일이 검사하는 O(n²) 방식 대신 선형 시간 O(n) 안에 효율적으로 답을 구할 수 있습니다.