누적합(prefix sum) 알고리즘

▶ 누적합(prefix sum) 알고리즘

---

누적합은 말 그대로 구간의 value를 누적합 형태로 구현하여 시간복잡도 측면에서 이득을 취하고자 하는 알고리즘이다.

 

일반적으로 사용되는 배열에 값을 저장하고 지정된 인덱스부터 하나씩 더해가는 방식은 최악의 경우 O(n^2)의 시간복잡도가 필요하기 때문에 입력 범위가 클 때 사용할 수 없다.

 

하지만 Prefix Sum방식의 누적합을 사용하면 입력과 동시에 누적합을 저장하고 필요한 구간의 값만 취하면 되기 때문에 O(n)으로 해결할 수 있다.

 

누적합은 문제에서 수열이 주어지고 어떤 구간의 합을 구해야할 때 쓰인다.

예를 들어 크기가 10인 배열에서 2번 index부터 8번 index 구간의 합을 구한다고 가정하면, 입력 후에 for문으로 다시 값을 구하는 것이 아닌 입력과 동시에 구간합을 저장하고

for(int i=1;i<=10;i++){
    cin >> arr[i];
    psum[i] = psum[i-1] + arr[i];
}

누적합은 psum[8] - psum[1]으로 표현할 수 있다.

 

 

 

 

1. 크기가 5인 배열 선언한 후 값 입력 → 누적합 저장

index	1	2	3	4	5
value	3	2	5	4	8
psum	3	5	10	14	22

 

 

 

.2. 3번에서 5번 구간 사이의 누적합 구하기  → 겹치는 1, 2구간을 제외 이는 2번 인덱스의 누적합을 빼야하는 것을 의미

int answer = psum[5] - psum[2];

 

 

 

추천문제

---

https://www.acmicpc.net/problem/2979

2979번: 트럭 주차

https://www.acmicpc.net/problem/11441

11441번: 합 구하기

https://www.acmicpc.net/problem/10025

10025번: 게으른 백곰