- Prefix sum(구간 합) : 구간 합이란 수들의 나열에서 특정 구간의 합을 의미한다. 구간 합 알고리즘은 보통 1차원배열에서 i~k 인덱스 사이의 값들의 합을 구하는데 사용한다.
- Partial sum(부분 합) : 부분 합이란 구간 합과 달리 처음부터 특정인덱스까지의 합을 의미한다. 즉 0~k 인덱스 사이의 값들의 합을 의미한다.
- 수열에서의 특정 구간 내 노드들의 합
연속적으로 나열된 N개의 수가 있을때, 특정 구간 내 모든 수를 더하는 알고리즘에 대해 파악한다.
다만, 단순히 1차원 리스트에서 선형탐색을 하며 합산하는 것이 아닌, 여러 정보와 구간이 제시될때 시간복잡도를 최소화하는 방안을 고민할 필요가 있다.
-
N개의 정수로 구성된 수열이 있을때, M개의 Query가 주어졌다고 한다.
-
각 Query는 [Left, Right] 정보가 담겨져 있고, Left부터 Right까지 해당 범위에 존재하는 모든 노드들의 합을 도출한다.
-
시간제한은 O(N+M)으로 제한한다(선형탐색으로 구성한다면 O(N^M)으로, 다른 방안이 필요).
- 접두사합(prefix sum) 알고리즘
매 Query마다 선형탐색을 하지 않고도 구간 합을 구하는데 시간복잡도를 최소화할 수 있는 방안 중 하나로, 접두사합 알고리즘(prefix sum)을 활용한다.
-
미리 각각의 숫자까지의 합(접두사 합)을 계산하여 미리 저장해 놓고, M개의 Query를 확인할 때마다 저장한 값을 그대로 활용하여 구간합을 구한다.
-
N개의 수, 각각의 위치에 대하여 접두사합을 계산하여 별도 리스트(P)에 저장한다.
각 구간의 합은, P[right] - P[left -1]이다.
- 알고리즘 구현
#접두사 합을 통한 구간 합 구하는 알고리즘 도출하기
n = 5
data = [10, 20, 30, 40, 50]
#sum result
sum = 0
#prefix sum, index = 0은 0으로 초기화, 노드1부터 계산하는 것임.
prefixSum = [0]
for i in data:
sum = sum + i
prefixSum.append(sum)
#구간합 계산
left = 3
right = 4
print(prefixSum[right]-prefixSum[left-1])
personal study area