정수 리스트로 구성할 수 있고, 필요할 때마다 인덱스 i부터 j-1까지의 요소 합을 효율적으로 구하는 기능을 제공하는 데이터 구조를 개발한다고 가정해 봅시다. 이 데이터 구조는 두 가지 기능을 가져야 합니다.
- 생성자(Constructor): 정수 배열을 받아 새로운 인스턴스를 생성합니다.
- get_sum(i, j): 시작 인덱스 i부터 끝 인덱스 j-1까지의 배열 요소 합을 반환합니다.
예를 들어, 입력이 array = [5,2,3,6,4,7,8,9,3,2]라고 하고 obj 객체를 생성한 후 obj.get_sum(1,5)와 obj.get_sum(4,8)을 호출하면 출력은 각각 15와 28이 됩니다. 첫 번째 범위의 요소는 [2,3,6,4]이므로 합은 15이고, 두 번째 범위의 요소는 [4,7,8,9]이므로 합은 28입니다.
해결 방법
이 문제를 해결하기 위해 누적 합(Prefix Sum) 기법을 활용합니다. 다음 단계를 따릅니다.
- 배열을 인자로 받는 생성자를 정의합니다.
- sums := 리스트를 생성하고 초기값 0을 삽입합니다.
- 배열의 각 요소 x에 대해 다음을 수행합니다.
- (x + sums의 마지막 요소)를 sums의 끝에 추가합니다.
- get_sum(i, j) 함수를 정의합니다.
- sums[j] - sums[i]를 반환합니다.
누적 합 배열을 미리 구성해 두면 각 쿼리를 O(1) 시간 복잡도로 처리할 수 있어 매우 효율적입니다. 전체 전처리 과정은 O(n)이며, 이후 몇 번이든 빠르게 범위 합을 조회할 수 있습니다.
예제 코드
다음 구현을 통해 더 잘 이해해 보겠습니다.
class RangeSum:
def __init__(self, array):
self.sums = [0]
for x in array:
self.sums.append(x + self.sums[-1])
def get_sum(self, i, j):
return self.sums[j] - self.sums[i]
array = [5,2,3,6,4,7,8,9,3,2]
obj = RangeSum(array)
print(obj.get_sum(1,5))
print(obj.get_sum(4,8))입력
[5,2,3,6,4,7,8,9,3,2] obj.get_sum(1,5) obj.get_sum(4,8)
출력
15 28
동작 원리 설명
생성자에서 sums 리스트는 [0]으로 시작합니다. 그런 다음 배열의 각 요소를 순회하면서 이전 누적 값에 현재 요소를 더한 값을 추가합니다. 위 예제의 경우 sums는 [0, 5, 7, 10, 16, 20, 27, 35, 44, 47, 49]가 됩니다.
get_sum(1,5)를 호출하면 sums[5] - sums[1] = 20 - 5 = 15가 되고, get_sum(4,8)을 호출하면 sums[8] - sums[4] = 44 - 16 = 28이 됩니다. 이렇게 두 누적 값의 차이만으로 원하는 범위의 합을 즉시 얻을 수 있습니다.