C++로 크기가 k인 부분 배열의 최대(또는 최소) 합 구하기 — 슬라이딩 윈도우 완벽 가이드

이 문제에서는 하나의 배열 arr[]과 숫자 k가 주어지며, 우리의 목표는 크기가 k인 부분 배열(subarray) 중에서 합이 최대(또는 최소)인 값을 찾는 것입니다.

문제 이해를 위한 예시

입력: arr[] = {55, 43, 12, 76, 89, 25, 99}, k = 2

출력: 165

설명:

크기가 2인 부분 배열 중 합이 가장 큰 경우는 76 + 89 = 165입니다.

해결 접근 방법

1. 단순한 방법 (브루트 포스)

가장 직관적인 방법은 크기가 k인 모든 부분 배열을 일일이 탐색한 뒤, 그중 합이 최대인 값을 반환하는 것입니다. 하지만 이 방법은 시간 복잡도가 O(n × k)로, 배열의 크기가 커지면 비효율적입니다.

2. 슬라이딩 윈도우(Sliding Window) 기법

더 효율적인 방법은 슬라이딩 윈도우 기법을 사용하는 것입니다. 먼저 첫 번째 크기 k짜리 부분 배열의 합을 계산하고, 그다음 부분 배열로 이동할 때는 윈도우에서 빠지는 맨 앞 요소를 빼고 새로 들어오는 요소를 더하는 방식으로 합을 갱신합니다.

이렇게 하면 매번 부분 배열의 합을 처음부터 다시 계산할 필요 없이 O(1)만에 업데이트할 수 있으며, 전체 시간 복잡도는 O(n)으로 크게 개선됩니다.

모든 윈도우를 순회한 후, 합이 최대인 값을 반환하면 됩니다.

해결 방법을 보여주는 프로그램

예제 코드

#include <iostream>
using namespace std;

int findMaxSumSubarray(int arr[], int n, int k) {
    
    // 배열의 크기가 k보다 작으면 유효하지 않음
    if (n < k) {
        cout << "Invalid";
        return -1;
    }

    // 첫 번째 윈도우의 합을 초기값으로 설정
    int maxSum = 0;
    for (int i = 0; i < k; i++)
        maxSum += arr[i];

    int curr_sum = maxSum;

    // 슬라이딩 윈도우: 앞 요소는 빼고, 새 요소는 더함
    for (int i = k; i < n; i++) {
        curr_sum += arr[i] - arr[i-k];
        maxSum = max(maxSum, curr_sum);
    }

    return maxSum;
}

int main() {
    
    int arr[] = {55, 43, 12, 76, 89, 25, 99};
    int n = sizeof(arr)/sizeof(arr[0]);
    int k = 2;
    cout << "크기가 " << k << "인 부분 배열의 최대 합은 " << findMaxSumSubarray(arr, n, k);
    return 0;
}

실행 결과

크기가 2인 부분 배열의 최대 합은 165

정리

슬라이딩 윈도우 기법을 활용하면 크기가 k인 부분 배열의 최대 합을 선형 시간 O(n)에 효율적으로 구할 수 있습니다. 최소 합을 구하는 경우에도 동일한 로직에서 비교 조건만 반대로 바꾸면 되므로, 이 패턴은 다양한 배열 문제에 폭넓게 응용될 수 있습니다.