C++ 코딩테스트 강좌, 연속 합 구하기

문제 설명

배열의 연속된 부분 수열의 합을 구하는 문제는 많은 코딩테스트에서 자주 등장하는 주제입니다. 이러한 문제는 제어 흐름, 배열 조작, 그리고 시간 복잡도를 고려하는 능력을 테스트하는 좋은 방법입니다. 이번 강좌에서는 ‘연속 합 구하기’라는 문제를 통해 이 주제를 심도 있게 다뤄보겠습니다.

문제 정의

주어진 정수 배열 arr에서 연속된 k개의 요소의 합을 구하는 함수를 작성하시오. 만약 arr의 길이가 n일 때, k는 1 이상 n 이하의 값을 가져야 합니다. 여기서, 사용자는 연속된 합을 구하기 위해서는 최적화된 방법을 사용해야 하며, 단순 루프를 사용하는 것은 추천하지 않습니다.

입력

첫 번째 줄에 정수 n (1 ≤ n ≤ 10^5)과 k (1 ≤ k ≤ n)이 주어집니다.
두 번째 줄에 n개의 정수로 이루어진 배열 arr가 주어집니다.

출력

연속된 k개의 요소의 합의 최댓값을 출력합니다.

예제

설명: 연속된 3개의 요소는 (3, 4, 5)로 총합은 12입니다.

문제 풀이 과정

이 문제를 풀기 위해서는 두 가지 주요 방법이 있습니다: 단순 반복을 통한 모든 조합 계산과 슬라이딩 윈도우(sliding window) 기법을 통한 최적화 접근법입니다.

1. 단순 반복 방식

단순 반복 방식을 사용하여 연속된 k개의 항목의 합을 계산할 수 있지만, 이 방법은 O(n*k)의 시간 복잡도를 가지기 때문에 배열의 크기가 커질 경우 비효율적입니다.

    void simpleSum(int arr[], int n, int k) {
        int maxSum = 0;
        for (int i = 0; i <= n - k; i++) {
            int currentSum = 0;
            for (int j = 0; j < k; j++) {
                currentSum += arr[i + j];
            }
            maxSum = max(maxSum, currentSum);
        }
        cout << maxSum << endl;
    }

2. 슬라이딩 윈도우 기법

슬라이딩 윈도우 기법은 연속된 k개의 요소의 합을 유지하면서 이전 값을 빼고 새로운 값을 더하는 방식으로 작동합니다. 이 접근법을 사용하면 시간 복잡도를 O(n)으로 줄일 수 있습니다.

    void slidingWindowSum(int arr[], int n, int k) {
        int maxSum = 0, currentSum = 0;

        // 첫 k개 요소의 합을 계산
        for (int i = 0; i < k; i++) {
            currentSum += arr[i];
        }
        maxSum = currentSum;

        // 슬라이딩 윈도우를 통해 합을 계산
        for (int i = k; i < n; i++) {
            currentSum += arr[i] - arr[i - k];
            maxSum = max(maxSum, currentSum);
        }
        
        cout << maxSum << endl;
    }

코드 구현

위의 두 방법 중 슬라이딩 윈도우 기법이 더 효율적이기 때문에 이 방법을 선택하여 전체 코드를 작성하겠습니다.

    #include <iostream>
    #include <algorithm>
    using namespace std;

    void slidingWindowSum(int arr[], int n, int k) {
        int maxSum = 0, currentSum = 0;

        // 첫 k개 요소의 합을 계산
        for (int i = 0; i < k; i++) {
            currentSum += arr[i];
        }
        maxSum = currentSum;

        // 슬라이딩 윈도우를 통해 합을 계산
        for (int i = k; i < n; i++) {
            currentSum += arr[i] - arr[i - k];
            maxSum = max(maxSum, currentSum);
        }
        
        cout << maxSum << endl;
    }

    int main() {
        int n, k;
        cin >> n >> k;
        int arr[n];
        for(int i = 0; i < n; i++) {
            cin >> arr[i];
        }
        slidingWindowSum(arr, n, k);
        return 0;
    }

결론

이 강좌에서는 ‘연속 합 구하기’라는 문제를 통해 배열의 연속된 부분 수열의 합을 구하는 방법을 살펴보았습니다. 슬라이딩 윈도우 기법을 사용하여 시간 복잡도를 O(n)으로 줄이는 최적화된 접근법을 사용함으로써 보다 효율적으로 코딩 테스트를 준비할 수 있기를 바랍니다.

참고 자료

– 알고리즘 문제 해결을 위한 기본 개념들
– C++ STL 활용하기
– 코드 최적화와 테스트 패턴