누적합(Prefix Sum) 알고리즘

누적합 알고리즘이란?

: 나열되어 있는 수를 누적되어 더해진 값을 말한다. 예를 들어 1, 2, 3, 4, 5 에서 첫 번째에서 두 번째까지의 수의 합은 3이고, 첫 번째부터 세 번째까지의 수의 합은 6이다. 첫 번째 수부터 마지막까지 더하면 15이다. 이것을 누적합이라고 한다.

 

 

누적합 알고리즘 설명

 

1) 1부터 5까지의 수열이 있다고 가정해보자. (빨간 숫자는 index이다.)

2) 누적합을 적용한 새로운 수열을 만들어주자.

위와 같이 새로운 누적합 수열은 첫 번째 수 + 두 번째 수, 첫 번째 수 + 두 번째 수 + 세 번째 수, ... 로 만들 수 있다.

새로운 누적합 수열의 해당 인덱스에는 처음 수부터 해당 인덱스까지의 합이 담겨 있다.

 

**그렇다면 특정 구간의 합은 어떻게 구할 수 있을까?

a번째부터 b번째까지의 합을 구하고 싶다면, 새로운 누적합 배열에서 [b번째] - [a번째 -1] 를 구하면 된다.

 

ex) 2번째 ~ 4번째의 누적합

 

방법 1) 2번째 ~ 4번째의 합 : 2+3+4 = 9

방법 2) 새로운 누적합 배열 4번째 - (2번째-1) : 10 - 1 = 9 

 

두 방법 모두 9가 나온다.  하지만 방법 2)를 사용하는 이유는 시간복잡도가 더 빠르기 때문이다.

 

 

예시) 백준 문제 #11659 : 구간 합 구하기4

 

다음과 같이 파이썬 코드로 나타낼 수 있다.

import sys
N, M = map(int, sys.stdin.readline().split(' '))
arr = list(map(int,sys.stdin.readline().split(' ')))
sum = 0

//새로운 누적합 배열
new_arr = [0] 
for k in range(N):
    sum += arr[k]
    new_arr.append(sum)


for _ in range(M):
    a, b = map(int, sys.stdin.readline().split(' ')) // 구간 a~b 의 누적합 구하기
    print(new_arr[b]-new_arr[a-1])

=> 여기에서 new_arr에 0을 대입해준 이유는 첫번째까지 누적합을 구할 때도 -1을 해줘야 하는데 문제가 발생하기 때문이다. 배열의 인덱스는 0번째부터 시작하기 때문에 첫번째 수에서 -1을 해주면 -1번째 인덱스가 호출이 된다. 그렇기 때문에 0번째에 0을 대입해준 것이다.

 

 

 

+투 포인터 

  : 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리 (시간 복잡도 : O(N))

1) 포인터 2개가 같은 방향으로 진행해 나가는 것

2) 포인터 2개가 양끝에서 반대로 진행하는 것

3) 포인터 하나는 한 쪽 방향으로만 진행하고, 다른 포인터는 양쪽으로 이동하는 것

 

 

예시) 백준 문제 #2003 : 수들의 합 2

 

 

다음과 같이 파이썬 코드로 나타낼 수 있다.

import sys
N, M = map(int, sys.stdin.readline().split())
arr = list(map(int, sys.stdin.readline().split()))

cnt = 0
sum = 0
end = 0

for start in range(N):
    while sum < M and end < N:
        sum += arr[end]
        end+=1    
    if sum == M :
        cnt +=1
    sum -= arr[start]

print(cnt)