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

이번 강좌에서는 구간 합을 구하는 두 번째 문제를 다룹니다. 구간 합 문제는 알고리즘과 데이터 구조에서 매우 중요한 주제로, 여러 상황에서 유용하게 사용됩니다. 효율적인 알고리즘을 통해 주어진 구간의 합을 계산하는 방법을 배울 것입니다.

문제 설명

다음과 같은 배열이 주어졌을 때, 여러 쌍의 시작 인덱스와 끝 인덱스가 주어질 것입니다. 각 쌍에 대해 구간의 합을 구하는 프로그램을 작성하세요.

입력

첫 번째 줄에 배열의 크기 N (1 ≤ N ≤ 100,000)과 질의의 수 M (1 ≤ M ≤ 100,000)이 주어진다.
두 번째 줄에 N개의 정수가 배열의 원소로 주어진다. 각 원소의 값은 -10,000 이상 10,000 이하이다.
이후 M개의 줄에 각각 두 개의 정수 S와 E가 주어지며, 이는 구간 [S, E]의 합을 구하는 것을 의미한다. (S, E는 1부터 시작하는 인덱스이다.)

출력

각 질의에 대한 구간 합을 각각의 줄에 출력한다.

문제 분석

구간 합 구하기 문제는 단순히 직접적으로 합을 계산할 경우 시간복잡도가 O(N)으로, M이 클 경우에는 O(N*M)으로 매우 비효율적입니다. 따라서 이런 경우에는 누적합(Prefix Sum) 기법을 사용하여 O(1)로 구간 합을 구할 수 있도록 개선합니다.

알고리즘

누적합 배열을 만든다.
각 질의에 대해 구간의 시작과 끝 인덱스를 사용하여 O(1) 시간에 구간 합을 구한다.

구현

이제 C++로 이 알고리즘을 구현해 보겠습니다.


#include <iostream>
#include <vector>

using namespace std;

int main() {
    int N, M;
    cin >> N >> M;
    
    vector<int> arr(N + 1, 0);
    vector<int> prefixSum(N + 1, 0);

    // 배열 입력
    for (int i = 1; i <= N; i++) {
        cin >> arr[i];
        prefixSum[i] = prefixSum[i - 1] + arr[i]; // 누적합 계산
    }

    // 쿼리 처리
    for (int i = 0; i < M; i++) {
        int S, E;
        cin >> S >> E;
        // 구간 합 계산
        cout << prefixSum[E] - prefixSum[S - 1] << endl;
    }

    return 0;
}

코드 설명

코드의 각 부분은 다음과 같은 작업을 수행합니다:

입력: N과 M을 입력 받고, 이후 N개의 숫자를 읽어 배열 arr에 저장합니다.
누적합 배열 생성: prefixSum 배열을 생성하여, i번째 원소까지의 합을 계산하여 저장합니다.
쿼리 처리: 각 쿼리에 대해 S와 E를 읽고, prefixSum을 활용하여 O(1) 시간에 구간 합을 계산합니다.

복잡도 분석

이 알고리즘의 시간 복잡도는 다음과 같습니다:

누적합 배열 생성: O(N)
각 쿼리에 대한 처리: O(M)
전체 시간 복잡도: O(N + M)

결론

이번 강좌에서는 구간 합을 효율적으로 계산하는 방법을 배웠습니다. 누적합 기법을 활용함으로써, 직접적인 반복을 피하고 시간 복잡도를 크게 줄일 수 있었습니다. 이러한 기법은 많은 문제에서 응용될 수 있으므로 꼭 숙지하시기 바랍니다.

다음 강좌에서는 좀 더 복잡한 데이터 구조를 사용한 구간 합 문제를 다룰 예정입니다. 감사합니다!

문제 설명

입력

출력

문제 분석

알고리즘

구현

코드 설명

복잡도 분석

결론

관련