[알고리즘] Prefix sum(구간 합)에 대해 알아보기

 안녕하세요. 오랜만의 알고리즘 포스팅입니다. 제가 방학이라고 공부 안 하고 놀아서 그렇습니다. (반성...) 이번 포스팅에서는 Prefix sum(구간 합)에 대해 알아보도록 하겠습니다. 아주 간단하지만 유용한 알고리즘입니다.

---

 Prefix sum?

 

 영어로는 이게 뭐지 싶지만 한글로 보면 의미를 대충 짐작하실 수 있을 겁니다. 구간 합이란 말 그대로 수들의 나열에서 특정 구간의 합을 의미합니다. 이와 비슷한 개념으로 부분 합이 있습니다. 부분 합은 구간 합과 달리 처음부터 특정 인덱스까지의 합을 의미합니다. 구간 합에서의 구간은 당연히 어느 구간이든 가능합니다. 처음부터 끝까지일 수도 있고, 세 번째에서 일곱 번째일 수도 있고, 마지막 숫자만일 수도 있겠습니다. 예를 들어 볼까요?

 

#include <stdio.h>
 
int main(void){
    int i, j, idx, sum = 0;
    int arr[6] = {0, 1, 2, 3, 4, 5};
    scanf("%d %d", &i, &j);
    for(idx = i; idx <= j; start++){
        sum += arr[idx];
    }
 
    return 0;
}

 

 다음의 코드는 원하는 구간을 입력받아 해당 구간의 구간 합을 구하는 코드입니다. 주어진 배열의 첫 번째 숫자인 0은 인덱스와 입력받은 구간을 일치시키기 위해 임의로 넣은 것입니다. 코드로 봐도 역시 간단합니다. 이 코드를 조금 수정해서, 부분 합을 통해 구간 합을 구해 보겠습니다.

 

#include <stdio.h>
 
int main(void){
    int i, j, idx, ans;
    int arr[6] = {0, 1, 2, 3, 4, 5};
    int sum[6] = {0, };
 
    for(idx = 0; idx < 6; idx++){
        if(idx == 0)
            sum[idx] = arr[idx];
        else
            sum[idx] = sum[idx-1] + arr[idx];
    }
 
    scanf("%d %d", &i, &j);
 
    ans = sum[j] - sum[i-1];
 
    return 0;
}

 

 이번에도 인덱스와 입력받은 구간을 일치시키기 위해 크기가 6인 배열을 선언했습니다. 구간 합과 비슷한 개념으로 부분 합이 있다고 했지만 부분 합이 구간 합보다 더 광위의 개념이라고 할 수 있겠습니다. 부분 합을 통해 우리는 구간 합을 구할 수 있습니다. 다들 고등학생 때 배운 수열의 부분 합을 떠올리셨을지도 모르겠네요. 그걸 그대로 코드로 옮겨 왔다고 해도 무방할 것 같습니다. 어쨌든 아주 간단한데, 그러면 이걸 도대체 어디에 쓸 거냐? 하는 의문이 슬슬 드실 수도 있겠습니다.

---

 Prefix sum&Query

 

 이 친구의 쓰임새는 쿼리와 함께 쓸 때 나타납니다. 쿼리는 데이터베이스에 정보를 요청하는 것을 말하는데, 간단히 말해서 요청 혹은 질문 정도라고 생각하면 되겠습니다. 만약 크기가 100000인 배열이 있고, 구간 합을 수천만 번 구해야 한다고 생각해 봅시다. 한 번 구할 때마다 매번 반복문을 사용하면 시간이 꽤나 걸릴 것입니다. 하지만 위에서 설명한 방식을 사용하면 훨씬 적은 시간을 들일 수 있습니다. 이것도 예시를 한번 들어 보겠습니다.

 

#include <stdio.h>
 
int main(void){
    int N, i, j, idx, ans;
    int arr[101];
    int sum[101] = {0, };
 
    for(idx = 0; idx < 6; idx++){
        arr[idx] = idx;
        if(idx == 0)
            sum[idx] = arr[idx];
        else
            sum[idx] = sum[idx-1] + arr[idx];
    }
 
    scanf("%d", &N);
    
    while(N--){
        scanf("%d %d", &i, &j);
        ans = sum[j] - sum[i-1];
        printf("%d", ans);
    }
 
    return 0;
}

 

 아주 간단한 예시이긴 하지만 구간 합을 구할 때 반복문을 사용하는 것보다 훨씬 더 간단해 보입니다. 실행 시간도 물론 훨씬 더 빠릅니다. 만약 N이 10000이라고 가정해 봅시다. for문을 사용하면  구간 합을 구하는 데에 O(j - i)만큼의 시간이 걸릴 것입니다. 구간은 처음부터 끝이 될 수도 있으므로 최악의 경우에는 배열의 크기와 같을 수도 있습니다. 배열의 크기를 M이라고 한다면 O(MN)의 시간이 걸리는 셈입니다. 하지만 위의 방법을 이용하면 구간 합은 상수 시간 내에 구할 수 있으므로 O(N)만큼의 시간이 소요되겠죠. 물론 모든 부분 합을 구하는 데에 시간이 걸리긴 하지만 이는 선형적이기 때문에 총 시간 복잡도는 O(M+N)이 될 것이고, 역시 O(MN)보다 낫습니다. 숫자가 커지면 커질수록 이쪽이 훨씬 효율적일 것입니다.

---

  이상으로 구간 합에 대해 알아보았습니다. 구간 합을 이용한 문제 풀기는 다른 포스팅으로 소개하도록 하겠습니다. 읽어 주셔서 감사합니다. (_ _)