[Algorithm/알고리즘] 누적합 알고리즘 Prefix Sum

 

A = [1, 2, 3, 4, 5]

# 부분합 = [1, 3, 6, 10, 15]

 

 

위와 같은 배열 A 가 있다. 이 배열의 각 부분합을 구해야 할 때 구할 수 있는 방법이 2가지 있다. 

 

 

 

1. 각 인덱스를 반복해서 돌면서 구하기

 

ans = 0

for i in range(start, end+1)
	ans += A[i]

위 코드의 시간 복잡도는 O(N) 이며, 각 부분합을 구하기 위해서는 배열의 크기만큼 위 코드를 반복해야 한다. 

 

ans = 0

for j in range(배열의 크기):
	for i in range(start, end+1)
		ans += A[i]

 

그러므로 총 시간 복잡도는 O(NM) 이 된다. (M: 배열의 크기인 임의의 수)

 

 

2. 누적 합 

 

누적 합 아이디어는 배열 A 에 들어있는 값이 바뀌지 않는다는 점을 이용한다. 배열이 변하지 않으니 구간의 합도 변하지 않는다. 따라서, 앞에서부터 차례대로 누적된 합을 구해놓고 이를 이용해서 구간의 합을 구할 수 있다. 

 

S[i] = A[1] + . . .  + A[i], S[0] = 0

 

s[0] = 0

for i in range(1, 배열의크기+1):
	s[i] = s[i-1] + A[i]

 

첫번째 방법과 다르게 배열의 for 문을 배열의 크기만큼만 돌면 되기 때문에 총 시간 복잡도는 O(M) 이 된다.

 

 

만약, j 번째 수부터 i 번째 수까지의 합을 구해야 한다면 s[i] - s[j-1] 을 하면 된다. (i >= j)

 

s[i] = A[1] + . . . A[j-1] + A[j] + . . .+ A[i]

s[j-1] = A[1] + . . . + A[j-1]

 

따라서 s[i] - s[j-1] = A[j] + A[j+1] + . . . + A[i]

 

구간의 합을 구하기 위한 뺄셈 연산의 시간 복잡도는 O(1), 연산을 배열의 크기 M 만큼 수행해야 하니 총 시간 복잡도는 O(1*M) = O(M) 이 된다. 

 

 

연습문제

11659 구간 합 구하기 4

2559 수열

10986 나머지 합