1. 구간 합 계산
백준이나, 프로그래머스 문제를 풀다보면 구간 합을 구해야 하는 문제가 종종 출제된다.
구간 합 문제란 연속적으로 나열된 N 개의 수가 있을 때, 특정 구간의 모든 수를 합한 값을 구하는 문제를 말한다.
예를 들어 5개의 데이터로 구성된 수열 {10, 20, 30, 40, 50}이 있다고 가정해보자.
여기에서 두 번째 수부터 네 번째 수까지의 합은 20 + 30 + 40으로 90이 될 것이다.
이러한 구간 합 계산 문제는 여러 개의 쿼리로 구성되는 문제 형태로 출제되는 경우가 많다.
다수의 구간에 대해서 합을 각각 구하도록 요구된다.
예를 들어 M개의 쿼리가 존재한다고 가정해보자.
각 쿼리는 Left와 Right로 구성되며, 이는 [Left, Right]의 구간을 의미한다.
결과적으로 M개의 쿼리가 주어졌을 때, 모든 쿼리에 대하여 구간의 합을 출력하는 문제가 전형적인 구간 합 계산 문제 이다.
만약 M개의 쿼리 각각, 매번 구간 합을 계산한다면 이 알고리즘은 O(NM)의 시간 복잡도를 가진다.
왜냐하면 M개의 쿼리가 수행될 때마다 전체 리스트의 구간 합을 모두 계산하라고 요구 할수도 있기 때문이다.
결과적으로 O(NM)의 시간 복잡도를 가지는 것이다.
그렇다면 N = 1,000,000 이고, M = 1,000,000인 상황처럼 데이터의 개수가 매우 많을 때, O(NM)의 시간 복잡도로 동작하는 알고리즘으로는 문제를 해결할 수 없을 것이다.
2. 접두사 합(Prefix Sum)
구간 합 계산을 위해 가장 많이 사용되는 기법이 바로 접두사 합(Prefix Sum)이다. 각 쿼리에 대해 구간 합을 빠르게 계산하기 위해서는 N개의 수의 위치 각각에 대하여 접두사 합을 미리 구해 놓으면 된다.
여기서 접두사 합이란 리스트의 맨 앞부터 특정 위치까지의 합을 구해 놓은 것을 의미한다.
구체적으로 접두사 합을 이용하여 구간 합을 빠르게 계산하는 알고리즘은 다음과 같다.
- N개의 수에 대하여 접두사 합(Prefix Sum)을 계산하여 배열 P에 저장한다.
- 매 M개의 쿼리 정보 [L, R]을 확인할 때, 구간 합은 P[R] - P[L-1]이다.
예를 들어 다음과 같이 5개의 데이터가 있다고 가정 해보자.
[10, 20, 30, 40, 50]
이 5개의 데이터에 대해서 접두사 합을 계산하면 다음과 같다.
[0, 10, 30, 60, 100, 150]
위에서 설명한 알고리즘대로 매 쿼리가 들어왔을 때, P[R] - P[L-1]을 계산하면 바로 구간 합을 구할 수 있게 된다.
따라서 매 쿼리당 계산 시간은 O(1)이 된다.
결과적으로 N개의 데이터와 M개의 쿼리가 있을 때, 전체 구간 합을 모두 계산하는 작업은 O(N + M)의 시간 복잡도를 가진다.
아래 코드는 위의 예시에대한 구현 코드이다.
n = 5
data = [10, 20, 30, 40, 50]
''' Make prefix sum array '''
summary = 0
prefix_sum = [0]
for i in data:
summary += i
prefix_sum.append(summary)
''' Get interval sum '''
left = 2 #2번째 수부터
right = 4 #4번째 수까지
print(prefix_sum[right] - prefix_sum[left - 1]) #구간합 구하기
댓글