구간 합

구간 합은 합 배열을 이용하여 시간복잡도를 줄이기 위해 사용하는 알고리즘

1. 구간 합 구하는 방법

합 배열 구하기

공식 : S[i] = S[i - 1] + A[i]

// 배열은 인덱스 0부터 시작하므로 크기를 한 칸 늘린 배열을 만들어서 첫번째부터 데이터가 담기도록 만듬
int[] A = {0, 1, 2, 3, 4, 5}
int[] S = new int[A.length + 1]

// 반복문을 1부터 A배열의 길이만큼 돌면서 합 배열 만듬
S[1] = S[0] + A[1]
S[2] = S[1] + A[2]
S[5] = S[4] + A[5]

// 합 배열을 구할 공간을 따로 만들지 않고 기존에 배열에다가 합 배열 데이터를 덮어씌워도 됨
A[1] = A[0] + A[1]
A[2] = A[1] + A[2]
A[5] = A[4] + A[5]

배열에서의 값은 인덱스 0부터 채워지는데 문제를 풀 때는 첫번째부터 N번째까지의 구간 합을 구하기 때문에
문제에서 두번째부터 네번째까지면 배열상에서는 첫번째부터 세번째까지에 해당되므로 배열의 공간을 +1 늘려서 문제와 맞춰야지 정확하게 풀 수 있음

i ~ j 까지의 구간 합

공식 : S[j] - S[i - 1]

int[] S = {0, 1, 3, 5, 9, 14} 

// 두번째 부터 네번째까지 구간 합 
// 첫번째 값을 버려야하니까 -1 감소 
S[4] - S[2 - 1]

// 첫번째 부터 네번째까지 구간 합 
S[4] - S[1 - 1]

해당 배열이 바뀌지 않으면 합 배열을 다시 구할 필요가 없기 때문에 효율적인데 배열의 값이 자주 바뀌면 합 배열도 다시 구해야되기 때문에 비효율적이게 됨 이러한 경우에는 세그먼트 트리를 사용함

2. 구간 합 알고리즘 문제1

백준 11659

1번 문제풀이

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    // 1.입력
    int N, M; // 데이터 개수, 합을 구할 횟수
    cin >> N >> M;

    vector<int> sumArr;  // 구간 합을 구할 대상 배열(데이터 개수에 따라서 배열 크기가 달라지니까 벡터 사용)    
    sumArr.push_back(0); // 0번째 인덱스는 사용 X

    for (int i = 1; i <= N; i++) {
        int value;
        cin >> value;
        sumArr.push_back(value);
    }

    // 2.합 배열       
    for (int i = 1; i <= N; i++) {
        // 첫번째 인덱스까지의 합 배열을 구하기 위해서는 0번째 인덱스와 첫번째 인덱스를 더해서 첫번째 인덱스에 넣어줌
        // 두번째 인덱스까지의 합 배열을 구하기 위해서는 첫번째 인덱스와 두번째 인덱스를 더해서 두번째 인덱스에 넣어줌
        int sumValue = sumArr[i - 1] + sumArr[i];
        sumArr[i] = sumValue;
    }

    // 3.구간 합 
    // 합을 구하는 구간 a~b 범위 입력        
    for (int i = 0; i < M; i++) {        
        int a, b;
        cin >> a >> b;
        int result = sumArr[b] - sumArr[a - 1];
        cout << result << "\n";
    }

    return 0;
}

2번 문제풀이

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    // 1.입력
    int N, M; // 데이터 개수, 합을 구할 횟수
    cin >> N >> M;
    int sumArr[100001];

    for (int i = 1; i <= N; i++) {        
        cin >> sumArr[i];        
    }

    // 2.합 배열       
    for (int i = 1; i <= N; i++) {    
        int sumValue = sumArr[i - 1] + sumArr[i];
        sumArr[i] = sumValue;
    }

    // 3.구간 합 
    // 합을 구하는 구간 a~b 범위 입력        
    for (int i = 0; i < M; i++) {        
        int a, b;
        cin >> a >> b;
        int result = sumArr[b] - sumArr[a - 1];
        cout << result << "\n";
    }

    return 0;
}

문제에서 배열에 들어갈 데이터 개수가 총 100,000개 이므로 0번째 인덱스를 제외한 총 100,001개의 크기의 배열을 만들어서 문제를 풀 수도 있지만 데이터의 개수가 적을 경우 사용되지 않는 나머지 공간은 낭비되므로 벡터를 사용하는게 좋지 않을까 생각함

그러나 벡터의 경우 동적 배열이기 때문에 확장 가능성을 고려해서 여유 메모리 공간을 더 할당해두므로 배열보다 더 큰 용량을 갖게됨 이 문제에서는 데이터의 개수가 적기 때문에 배열을 사용하는게 더 효율적임

 

3번 문제풀이

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    // 1.입력
    int N, M; // 데이터 개수, 합을 구할 횟수
    cin >> N >> M;
    int sumArr[100001];

    for (int i = 1; i <= N; i++) {        
        cin >> sumArr[i];        
    }

    // 2.구간 합 
    // 합을 구하는 구간 a~b 범위 입력        
    for (int i = 0; i < M; i++) {        
        int a, b;
        cin >> a >> b;

        // 2.1. b까지의 합 구하기 
        int bSum;
        for (int j = 1; j <= b; j++) {
            bSum += sumArr[j];
        }
        // 2.2. a 이전까지의 합 구하기 
        int aSum;
        for (int j = 1; j < a; j++) {
            aSum += sumArr[j];
        }
        // 2.3. a~b까지의 합 구하기 
        int result = bSum - aSum;
        cout << result << "\n";
    }

    return 0;
}

해당 문제는 0.5초 안에 모든 구간의 합 계산을 끝내야 하는데 최악의 경우 a~b까지의 구간 합을 구할 때 a가 1이고 b가 N인 경우 시간 복잡도는 O(N)으로 제한시간 안에 풀지 못함
(Q1. 시간복잡도는 왜? O(N)일까?)