[Algorithm] 부분합(Partial Sum) ; 누적합(Prefix Sum)

부분합(Partial Sum) ; 누적합(Prefix Sum)

연속된 구간 $start$ 부터 $end$ 까지의 합 구하기

• 일차원 배열 a가 아래와 같이 초기화되어 있다.

X	10	20	30	40	50	60	70	80	90	100
a[0]	a[1]	a[2]	a[3]	a[4]	a[5]	a[6]	a[7]	a[8]	a[9]	a[10]

• 배열 a에서 연속된 구간 $start$ 부터 $end$ 까지의 합을 $\displaystyle \sum_{k=\text{start}}^{\text{end}} a[k] = a[start] + a[start + 1] + \cdots + a[end -1] + a[end]$ 로 정의한다면 ($start ≤ end$), 구간 5부터 구간 9까지의 합 $\displaystyle \sum_{k=5}^{9}a[k] (= a[5] + a[6] + a[7] + a[8] + a[9] = 50 + 60 + 70 + 80 + 90)$ 는 $350$ 이 된다.
• 연속된 구간의 합을 단 한 번만 구하고자 한다면, 다음과 같이 for 문을 이용하여 코드를 작성하여도 전혀 무리는 없을 것이다.

for (int i = start; i <= end; i++) {
    sum += a[i];
}

 

• 그러나 필요에 따라서 연속된 구간의 합을 여러 번 구해야할 때가 있는데, 그럴 때마다 매번 for 문의 순환이 발생하게 된다면 시간적인 효율성이 상당히 떨어지는 코드가 될 것이다.
• 이런 경우에 부분합(Partial Sum)을 이용한다면 연속된 특정 구간의 합을 쉽게 구할 수 있다.

 

부분합 구하기

X	10	30	60	100	150	210	280	360	450	550
s0]	s[1]	s[2]	s[3]	s[4]	s[5]	s[6]	s[7]	s[8]	s[9]	s[10]

• 우선 또 다른 배열 $s$ 를 선언하고, $s[1]$ 에는 $\displaystyle \sum_{k=1}^{1} a[k]$ 의 값 $a[1]$ 를, $s[2]$ 에는 $\displaystyle \sum_{k=1}^{2} a[k]$ 의 값 $a[1] + a[2]$ 를, $s[3]$ 에는 $\displaystyle \sum_{k=1}^{3} a[k]$ 의 값 $a[1] + a[2] + a[3]$ 을, …, 마지막으로 $s[10]$ 에는 $\displaystyle \sum_{k=1}^{10} a[k]$ 의 값 $a[1] + a[2] + \cdots + a[10]$ 을 구한다.
• 즉, $s[n]$ 번째는 $\displaystyle \sum_{k=1}^{n} a[k]$ 의 값 $a[1] + a[2] + \cdots + a[n]$ 을 구한다.

for (int i = 1; i <= 10; i++) {
    s[i] = s[i - 1] + a[i];
}

 

• $s[0]$ 의 값이 0으로 초기화되어 있고, $s[1]$ 은 $s[0]$ 과 $a[1]$ 를 더해서 $s[0] + a[1] = 0 + 10 = 10$ 이 된다.
• $s[2]$ 는 $\displaystyle \sum_{k=1}^{1} a[k]$ 에다 $a[2]$ 를 더해서 $s[1] + a[2] = 10 + 20 = 30$ 이 된다.
• $s[3]$ 는 $\displaystyle \sum_{k=1}^{2} a[k]$ 에다 $a[3]$ 를 더해서 $s[2] + a[3] = 30 + 30 = 60$ 이 된다.
• 이와 같은 방법으로 구간 1부터 n까지의 합 $\displaystyle s[n](=\sum_{k=1}^{n} a[k])$ 을 구하기 위해서 이것을 일반화시키면 $\displaystyle \sum_{k=1}^{n-1}a[k]$ 에다 $a[n]$ 를 더해서 $s[1]$ 부터 $s[n]$ 까지 값들을 단 한 번의 순환으로 모두 구할 수 있다.

cout << s[end] - s[start - 1] << endl;

• 연속된 구간 $start$ 부터 $end$ 까지의 합 $\displaystyle \sum_{k=\text{start}}^{\text{end}} a[k]$ 를 구하기 위해서는 구간 1부터 구간 $end$ 까지의 합 $\displaystyle \sum_{k = 1}^{\text{end}} a[k]$ 에서 구간 1부터 구간 $start$ - 1까지의 합 $\displaystyle \sum_{k = 1}^{\text{start} - 1} a[k]$ 의 값을 빼면$\displaystyle \sum_{k=\text{start}}^{\text{end}} a[k]$ 의 값을 구할 수 있다.

  a[1] + a[2] + a[3] + ... + a[start - 1] + a[start] + ... + a[end - 1] + a[end]
- a[1] + a[2] + a[3] + ... + a[start - 2] + a[start - 1]
------------------------------------------------------------------------------------------------
= a[start] + a[start + 1] + ... + a[end - 1] + a[end]

 

예제 : 구간 5부터 9까지의 합 $\displaystyle \sum_{k=5}^{9} a[k]$ 구하기

• 구간 1부터 구간 9까지의 합 $\displaystyle \sum_{k=1}^{9} a[k] = s[9] = 450$ 이 된다.
• 450은 처음부터 구간 9까지의 합 $a[1] + a[2] + a[3] + \cdots + a[9]$ 이므로, 여기서 처음부터 구간 4까지의 합 $\displaystyle \sum_{k=1}^{4} a[k] = s[4] = 100$, 즉 $a[1] + a[2] +a[3] + a[4]$ 를 빼면 $\displaystyle \sum_{k=5}^{9} a[k] = a[5] + a[6] + a[7] + a[8] + a[9] = 450 - 100 = 350$ 이 된다.

 

알고리즘

#include <iostream>
using namespace std;

int main() {
    int a[11] = { 0, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 }, s[11];
    int start, end;
    
    s[0] = 0;
    for (int i = 1; i <= 10; i++) {
        s[i] = s[i - 1] + a[i];
    }
    
    // 구간 5부터 구간 9까지의 부분합 구하기
    start = 5, end = 9;
    cout << s[end] - s[start - 1] << endl;
    
    return 0;
}

350

 

누적 합(Prefix Sum) vs. 부분 합(Partial Sum)

누적 합(Prefix Sum)

• 수들의 나열에서 특정 구간의 합
• 구간 합이라고도 불린다.
• 보통 1차원 배열에서 @i ~ k@ 인덱스 사이의 값들의 합을 구하는데 사용한다.

 

부분 합(Partial Sum)

• 처음부터 특정 인덱스까지의 합
• @0 ~ k@ 인덱스 사이의 값들의 합을 구하는데 사용한다.