C++ 코딩테스트 강좌, 구간 합 구하기 1

안녕하세요! 이번 시간에는 C++ 코딩테스트에서 자주 등장하는 ‘구간 합’ 문제를 통해 알고리즘 문제 해결 능력을 키워보겠습니다. 구간 합 문제는 주어진 배열의 특정 구간에 속한 요소들의 합을 구하는 문제로, 이 문제를 해결하기 위한 다양한 방법과 최적화 기법을 알아보도록 하겠습니다.

문제 설명

주어진 정수 배열 A와 정수 M이 있습니다. 우리는 A의 각 요소에 대해 A[i]에서 시작하는 구간의 합을 A[i] + A[i+1] + ... + A[j]의 형태로 구해야 합니다. 아래는 문제의 구체적인 요구 사항입니다.

문제

정수 배열 A와 정수 M이 주어졌을 때, A[i]에서 시작해 M개의 연속된 원소들의 합을 구하는 함수를 구현하시오.

입력

첫 번째 줄에 배열의 길이 N이 주어진다. (1 ≤ N ≤ 100,000)
두 번째 줄에 N개의 정수로 이루어진 배열 A가 주어진다. (−1,000,000,000 ≤ A[i] ≤ 1,000,000,000)
세 번째 줄에 정수 M이 주어진다. (1 ≤ M ≤ N)

출력

구간 합을 출력하시오. 만약 A[i]에서 시작해 M개 원소의 합이 가능한 경우, 그 합을 출력하고, 그렇지 않은 경우 -1을 출력하시오.

해결 과정

이 문제를 해결하기 위해 여러 가지 접근 방식이 있을 수 있지만, 가장 일반적이고 효율적인 방법은 슬라이딩 윈도우(Sliding Window) 기법을 사용하는 것입니다. 슬라이딩 윈도우 기법을 사용하면 O(N)의 시간 복잡도로 문제를 해결할 수 있습니다.

슬라이딩 윈도우 접근법 설명

슬라이딩 윈도우 기법에서는 구간의 시작과 끝을 창과 같이 설정하여, 그 창을 이동시키면서 해당 구간의 값을 계산합니다. 초기 구간을 설정한 후, 다음 요소를 추가하고 시작점의 요소를 빼면서 구간의 합을 갱신합니다. 이를 통해 불필요한 계산을 줄이고 효율성을 높일 수 있습니다.

코드 구현

이제 우리의 접근 방식을 C++로 구현해 보겠습니다.


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

// 함수: 구간 합 구하기
long long rangeSum(const vector<int> &A, int M) {
    long long sum = 0; // 초기 합 변수
    int N = A.size(); // 배열 크기

    // 첫 번째 구간의 합을 구한다
    for (int i = 0; i < M; i++) {
        sum += A[i];
    }
    
    // 첫 번째 구간 합을 출력
    cout << "구간 합: " << sum << endl;

    // 슬라이딩 윈도우로 구간 합 갱신
    for (int i = M; i < N; i++) {
        sum += A[i] - A[i - M]; // 기존 요소 빼고 새로운 요소 더하기
        cout << "구간 합: " << sum << endl; // 갱신된 구간 합 출력
    }
    
    return sum; // 최종 반환값
}

int main() {
    int N, M;
    cout << "배열의 길이 N: ";
    cin >> N; // 배열 크기 입력받기
    vector<int> A(N);

    cout << "정수 배열 A: ";
    for (int i = 0; i < N; i++) {
        cin >> A[i]; // 배열 원소 입력받기
    }

    cout << "구간의 길이 M: ";
    cin >> M; // 구간 합의 길이 입력받기

    long long totalSum = rangeSum(A, M); // 구간 합 함수 호출
    if (N < M) {
        cout << "-1" << endl; // 구간 합이 불가능한 경우 -1 출력
    } else {
        cout << "구간 합의 총합: " << totalSum << endl; // 총합 출력
    }

    return 0;
}

코드 설명

위 코드는 다음과 같은 과정을 거쳐 구간 합을 구하는 과정을 보여줍니다.

먼저, 크기 N의 배열 A와 구간 길이 M을 입력받습니다.
구간의 초기 합을 계산하기 위해 첫 번째 M개의 원소를 더합니다.
슬라이딩 윈도우 기법을 적용하여, 다음 구간 합을 얻기 위해 기존의 요소를 빼고 새로운 요소를 더합니다.
모든 구간의 합을 출력합니다.

결론

이번 시간에는 C++을 이용해 구간 합을 구하는 문제를 해결해 보았습니다. 슬라이딩 윈도우 기법은 아주 간단하면서도 효율적인 방법이라, 다양한 문제를 해결하는 데 유용하게 사용할 수 있습니다. 이와 같은 기법을 익혀두면 코딩 테스트를 준비하는 데 많은 도움이 될 것입니다.

다음 강좌에서는 더욱 다양한 문제를 다루고 더 깊이 있는 알고리즘의 이해를 도와드리겠습니다. 그럼 다음 시간까지 연습하시고 좋은 결과 있으시길 바랍니다!

문제 설명

문제

입력

출력

해결 과정

슬라이딩 윈도우 접근법 설명

코드 구현

코드 설명

결론

관련