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

구간 합 문제는 주어진 배열 안에서 특정 범위의 합을 효율적으로 구하는 알고리즘 문제입니다. 이 문제는 다양한 프로그래밍 언어에서 자주 등장하며, 특히 C++에서의 구현이 중요합니다. 이번 강좌에서는 구간 합 문제에 대해 구체적인 문제를 설정하고, 이를 해결하기 위한 과정을 상세히 설명하겠습니다.

1. 문제 설명

다음과 같이 정수로 구성된 배열이 주어졌다고 가정해봅시다. 정수 배열 A의 크기는 N입니다. 우리는 M개의 쿼리를 통해 배열의 특정 구간의 합을 계산해야 합니다. 구간의 시작 인덱스는 L, 끝 인덱스는 R로 주어지며, 우리는 A[L] + A[L+1] + ... + A[R]를 계산해야 합니다.

예를 들어, 배열 A가 다음과 같다고 합시다:

A = [10, 20, 30, 40, 50]

그리고 다음과 같은 쿼리가 주어졌다고 가정해봅시다:

1. L = 1, R = 3
2. L = 0, R = 4
3. L = 2, R = 2

주어진 쿼리에 대한 구간 합을 구하면 다음과 같습니다:

1. A[1] + A[2] + A[3] = 20 + 30 + 40 = 90
2. A[0] + A[1] + A[2] + A[3] + A[4] = 10 + 20 + 30 + 40 + 50 = 150
3. A[2] = 30

2. 문제 해결 접근 방법

구간 합 문제를 해결하기 위한 전통적인 방법은 직접 배열을 순회하는 것입니다. 그러나 이는 비효율적일 수 있습니다. 예를 들어, M개의 쿼리에서 각 쿼리마다 O(R - L + 1)의 시간이 소모된다면 최악의 경우 O(N * M)의 시간이 걸리게 됩니다. 이를 개선하기 위해 다음과 같은 방법을 사용합니다.

2.1. 전처리 방식 – 누적 합 배열

모든 쿼리의 합을 빠르게 계산하기 위해 누적 합 배열을 활용할 수 있습니다. 먼저 주어진 배열 A의 누적합 배열 S를 정의합니다. 누적합 배열은 다음과 같이 계산됩니다:

S[i] = S[i - 1] + A[i]

여기서 S[0]는 0으로 초기화됩니다. 누적합 배열을 사용하면 구간의 합을 다음과 같이 쉽게 구할 수 있습니다:

sum(L, R) = S[R] - S[L - 1]

이제 구간 합을 O(1)의 시간복잡도로 계산할 수 있습니다. 아래는 누적 합 배열을 사용하는 C++ 해결 방법입니다.

3. C++ 코드 예제

#include 
#include 
using namespace std;

int main() {
    int N, M;
    cin >> N >> M;

    vector A(N);
    vector S(N + 1, 0); // S[0]은 0으로 초기화

    for (int i = 0; i < N; i++) {
        cin >> A[i];
        S[i + 1] = S[i] + A[i]; // 누적 합 계산
    }

    for (int i = 0; i < M; i++) {
        int L, R;
        cin >> L >> R;
        // 구간 합 출력
        cout << S[R] - S[L - 1] << endl;
    }
    return 0;
}

4. 코드 설명

위 코드를 단계별로 설명하겠습니다:

입력 받기: 배열의 크기 N과 쿼리 수 M을 입력받고, 배열 A의 값을 입력받습니다.
누적 합 배열 생성: 각 인덱스에 대해 누적 합을 계산하여 S 배열에 저장합니다. 이 배열은 원본 배열 A의 값들의 합을 쉽게 찾아올 수 있게 돕습니다.
쿼리 처리: 각 쿼리마다 구간의 시작 및 끝 인덱스 L와 R을 입력받고, 누적 합 배열 S를 통해 구간의 합을 계산하여 출력합니다.

5. 성능 분석

위의 C++ 코드의 시간 복잡도는 배열 A의 누적합을 계산하는 데 O(N), 각 쿼리를 처리하는 데 O(1)이므로 전체 시간 복잡도는 O(N + M)입니다. 이는 매우 효율적인 방법으로, 수천 개의 쿼리에서도 빠른 시간 내에 결과를 얻을 수 있습니다.

6. 다양한 변형 문제

구간 합 문제는 여러 가지 변형이 가능합니다. 예를 들어:

구간 최소값/최대값: 주어진 파라미터에 대한 최소값이나 최대값을 찾는 문제로 변형 가능.
구간 업데이트: 특정 범위의 값을 변경한 후 다시 구간 합을 계산해야 하는 경우. 이 경우 세그먼트 트리를 활용할 수 있습니다.
2차원 구간 합: 2차원 배열에서 특정 구간의 합을 계산하는 문제로, 이중 누적합을 사용할 수 있습니다.

7. 마무리

구간 합 문제는 프로그래밍에서 매우 유용한 기술 중 하나이며, 특히 대규모 데이터 처리가 필요한 경우 상당한 효율성을 제공합니다. 이번 강좌에서는 누적 합 배열을 이용하여 구간 합 문제를 해결하는 방법을 알아보았습니다. 다양한 변형 문제를 통해 이 기술을 더욱 발전시킬 수 있습니다. 여러 문제를 풀어보며 경험을 쌓고, C++ 코딩 테스트에서 높은 점수를 얻기를 바랍니다.

강좌를 마치며, 추가적인 질문이나 요청 사항이 있을 경우 댓글로 남겨주세요.