[Algorithm] 누적 합(Prefix sum)을 이용한 구간 합 구하기 기본 문제
누적 합(Prefix sum)을 이용해서 구간 합을 구해보자
환경 및 선수조건
- C, C++
문제
문제 링크
- 백준 11659번 문제
- 문제 링크: https://www.acmicpc.net/problem/11659
- 문제: 수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.
접근법 및 풀이법
(방법1)
- N개의 수를 배열에 입력받고 i부터 j까지의 합을 입력이 올 때마다 계산해서 반환
- 시간복잡도:
O(n^2)
(방법2)
- Prefix sum을 구해두고
sum(i)(처음부터 i까지의 합) - sum(j-1)(처음부터 j-1까지의 합)을 통해서 반환 - 시간복잡도:
O(n)
누적합(Prefix Sum, Cumulative Sum)이란?
정의
누적합(Cumulative Sum) 또는 부분합(Prefix Sum): x0, x1 … xN까지 수가 있을 때 y0=x0, y1=x0+x1 … yN=x0+x1+…+xN처럼 해당 N까지의 합을 의미합니다.
y0 = x0
y1 = x0 + x1
y2 = x0 + x1 + x2
...
yN = x0 + x1 + ... + xN
누적합의 성질
- 특정 위치 i부터 j까지의 합은 아래의 공식으로 나타낼 수 있습니다.
S[j] - S[i-1] = a[i] + a[i+1] + ... + a[j-1] + a[j]
풀이
방법1 - O(n^2)
- 매번 요청이 올때마다 합을 구합니다.
#include <cstdio>
#define MAX_N 100001
#define MAX_M 100001
using namespace std;
int value[MAX_N];
int main(){
int N, M;
scanf("%d %d", &N, &M);
for(int i = 1; i <= N; ++i){
scanf("%d", &value[i]);
}
while(M--){
int from, to;
scanf("%d %d", &from, &to);
int sum = 0;
for(int i = from; i <= to; ++i){
sum += value[i];
}
printf("%d\n", sum);
}
return 0;
}
방법2 - O(n)
- 매번 요청이 올때마다 미리 구해놓은 sum배열을 이용해 값을 바로 반환합니다.
#include <cstdio>
#define MAX_N 100001
#define MAX_M 100001
using namespace std;
int value[MAX_N];
int sum[MAX_N];
int main(){
int N, M;
scanf("%d %d", &N, &M);
for(int i = 1; i <= N; ++i){
scanf("%d", &value[i]);
sum[i] = sum[i-1] + value[i];
}
while(M--){
int from, to;
scanf("%d %d", &from, &to);
printf("%d\n", sum[to] - sum[from - 1] );
}
return 0;
}