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

문제 접근 방법

구간 합 문제는 여러 가지 방법으로 해결할 수 있지만, 효율적인 방법으로는
누적 합(Prefix Sum)을 활용한 접근 방식이 있습니다. 누적 합을 통해 주어진 구간
[left, right]의 합을 O(1)의 시간 복잡도로 계산할 수 있습니다.

기본적인 아이디어는 배열의 각 인덱스까지의 합을 미리 계산하여 저장하는 것입니다.
이를 통해 특정 구간의 합은 다음과 같이 구할 수 있습니다.

sum(left, right) = prefixSum[right] - prefixSum[left - 1]

여기서 prefixSum[i]는 배열의 처음부터 i번째 요소까지의 합입니다.
이 방법은 배열을 한 번 순회하는 O(N)의 복잡도를 가지고 있으며, 이후 각 구간 합은 O(1)로 계산할 수 있습니다.

구현

코드

#include <iostream>
#include <vector>

using namespace std;

class SubarraySum {
public:
    SubarraySum(const vector<int>& arr) {
        int n = arr.size();
        prefixSum.resize(n + 1);
        prefixSum[0] = 0; // prefixSum[0]은 0으로 초기화합니다.
        
        for (int i = 1; i <= n; i++) {
            prefixSum[i] = prefixSum[i - 1] + arr[i - 1];
        }
    }

    int getSum(int left, int right) {
        return prefixSum[right] - prefixSum[left - 1];
    }

private:
    vector<int> prefixSum; // 누적 합을 저장하는 배열입니다.
};

int main() {
    int n; // 배열의 크기
    cout << "배열의 크기를 입력하세요: ";
    cin >> n;
    vector<int> arr(n);
    cout << "배열의 원소를 입력하세요: ";
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    SubarraySum subarray(arr);

    int left, right;
    cout << "구간의 왼쪽 경계를 입력하세요 (1부터 시작): ";
    cin >> left;
    cout << "구간의 오른쪽 경계를 입력하세요: ";
    cin >> right;

    int result = subarray.getSum(left, right);
    cout << "구간 [" << left << ", " << right << "]의 합은: " << result << endl;

    return 0;
}
    

코드 설명

클래스 정의

SubarraySum 클래스는 구간 합을 계산하는 기능을 제공합니다.
이 클래스의 생성자에서 배치된 배열의 원소를 기반으로 누적 합을 초기화합니다.
배열의 크기를 저장하는 n 변수를 정의하고, prefixSum 배열을(`[0]`을 하나 포함하여) 생성합니다.

누적 합 계산

생성자 내부의 for 루프를 통해 배열을 순회하여
각 인덱스까지의 합을 prefixSum 배열에 저장합니다.
이는 배열의 첫 번째 인덱스부터 시작하기 때문에 배열의 크기보다 1 큰 크기를 가지는 것이 특징입니다.

구간 합 계산

getSum(int left, int right) 메소드는 주어진 left와 right 인덱스를
사용하여 구간 합을 반환합니다. 누적 합 배열의 값을 이용하여 간단히
prefixSum[right] - prefixSum[left - 1] 로 구간 합을 계산할 수 있습니다.

테스트 및 활용

본 코드를 통해 사용자는 구간의 왼쪽과 오른쪽 경계를 입력받고,
해당 구간의 합을 쉽게 계산할 수 있습니다. 이 알고리즘은 입력 배열의 크기가 커져도
매끄럽게 동작하며, 구간 합을 O(1)의 시간 복잡도로 신속하게 처리할 수 있는 장점을 가집니다.

결론

구간 합 문제는 다양한 응용 프로그램에서도 널리 사용되며,
이러한 누적 합 방식은 데이터 분석, 통계 처리 등 여러 분야에서 유용성을 보여줍니다.
이 간단하지만 뛰어난 방법을 통해 문제 해결의 효율성을 높일 수 있습니다.

이 강좌가 여러분의 C++ 코딩 테스트 준비에 도움이 되길 바랍니다!