구간 합(Prefix Sum) 알고리즘

---

목차

1. 구간 합(Prefix Sum)이란?

2. 구간 합(Prefix Sum)이 어디에 쓰일까?

3. Prefix Sum Algorithm

4. Prefix Sum이 쓰이는 문제들

---

1. 구간 합(Prefix Sum)이란?

공부를 하다보면 부분 합, 구간 합의 개념이 헷갈릴 때가 있다.

부분 합은 0~k까지의 합을 의미하는 것이고 

구간 합은 a~b까지의 합을 의미하는 것이다.

이러한 구간 합(Prefix Sum)을 구하는 간단한 알고리즘이 존재하기에 소개하고자 한다.

2. 구간 합(Prefix Sum)이 어디에 쓰일까?

아래와 같은 문제가 주어진다 생각해보자.

int arr[10] = {0, 2, 3, 4, 5, 6, 7, 8, 9} 배열이 존재한다.

이때 a에서 b의 구간 합을 요구하는 쿼리 2천만개가 들어온다.

이러한 문제에 대해 어떻게 해결 할 것인가? 

가장 쉬운 방식은 다음과 같다.

#include <iostream>
#include <cstdio>
 
using namespace std;
 
int main()
{
    int arr[10] = { 0,1,2,3,4,5,6,7,8,9 };
 
    int n; // 쿼리 수
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++)
    {
        int a, b;
        scanf("%d %d", &a, &b);
 
        int sum = 0;
        for (int j = a; j <= b; j++)
            sum += arr[j];
 
        printf("%d\n", sum);
    }
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

'이렇게 구하면 되지 뭐가 문제인가요?'

맞다. 사실 이렇게 구하면 못구할 것도 없다.

하지만 쿼리 2천만개를 1초만에 해결해달라고 요구하였을 때, 이 코드의 시간 복잡도를 보자

쿼리 2천만개 * (a에서 b의 합 구하는 for문의 최악의 경우는 a = 0, b = 9일때 즉 10)

따라서 O(20,000,000 * 10) = O(200,000,000) 대략 2초이다.

결국 문제 의뢰인의 요구사항을 해결하지 못하게 된다.

이러하기에 우리는 Prefix Sum이라는 알고리즘을 공부하고자 한다.

3. Prefix Sum Algorithm

위의 코드에서 뭐가 바뀐지도 모를 만큼의 약간의 수정을 통해 이 알고리즘은 완성된다.

#include <iostream>
#include <cstdio>
 
using namespace std;
 
int main()
{
    int arr[10] = { 0,1,2,3,4,5,6,7,8,9 };
    int sum[10] = { 0, };
 
    for (int i = 0; i < 10; i++)
    {
        if (i == 0)
            sum[i] = arr[i];
        else
            sum[i] = sum[i - 1] + arr[i];
    }
 
    int n; // 쿼리 수
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++)
    {
        int a, b;
        scanf("%d %d", &a, &b);
 
        printf("%d\n", sum[b] - sum[a-1]);
    }
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

for문이 2중 포문에서 단일 포문으로 변하였다.

그리고 sum 배열이 생겨 sum을 미리 계산해 두고 있다.

저 sum 배열의 의미는 sum[0] :: 0번째까지 합, sum[1] :: 1번째까지 합, sum[k] :: k번째까지 합 (arr의 k번째까지라는 의미)

이렇게 된다면 이제 쿼리는 sum[b] - sum[a - 1]을 하면 답이 나오기에 O(1)에 끝이난다.

그렇다면 시간 복잡도는 쿼리 2천만개 * 1 = O(20,000,000) = 0.2초가 된다.

4. Prefix Sum이 쓰이는 문제들

이제 이 알고리즘이 언제 쓰이는지 문제들을 통해 알아보자.

[11441번] 합 구하기 :: https://www.acmicpc.net/problem/11441

[1806번] 부분합 :: http://www.crocus.co.kr/595

[1644번] 소수의 연속합 ::  http://www.crocus.co.kr/599

[2015번] 수들의 합 4 ::  http://www.crocus.co.kr/602

[Codeground 42번] 부분배열 ::  http://www.crocus.co.kr/841