반응형


목차


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천만개가 들어온다.


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


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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <cstdio>
 
using namespace std;
 
int main()
{
    int arr[10= { 0,1,2,3,4,5,6,7,8,};
 
    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 >>
Crocus



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


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


하지만 쿼리 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


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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
#include <cstdio>
 
using namespace std;
 
int main()
{
    int arr[10= { 0,1,2,3,4,5,6,7,8,};
    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 >>
Crocus



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




반응형