[Algorithm] 합배열(Prefix Sum)과 구간 합(Range Sum)
합 배열 및 구간 합 알고리즘에 대해 알아보자
배열코딩테스트알고리즘자바
🥅 들어가며
코딩 테스트 준비를 하다보면 배열과 관련해서 구간 합(Range Sum)에 대한 문제를 마주하게 된다.구간합이란 간단하게 말하면 배열의 특정 구간 내의 원소들의 합을 구하는 문제이다. 굳이 코딩 테스트가 아니어도 특정 기간의 통계량을 계산하는 여러 현실 문제에 대해 구간 합은 자주 쓰이는 개념이다. 이러한 구간합을 어떻게 효율적으로 구할 수 있는지 알아보자.
➕ 합 배열의 개념 및 구간 합의 계산
구간합을 시간 복잡도를 고려하여 가장 효율적으로 계산하는 방법은 합배열(Prefix Sum) 이다. 합배열이란 배열의 누적 합을 저장하는 배열이다. 배열 A가 {1, 2, 3, 4, 5} 라면 합배열 S는 {1, 3, 6, 10, 15} 인 식이다. 수식으로는 다음과 같다.
이렇게 구한 합배열 S를 이용하여 배열 A의 구간합을 쉽게 구할 수 있다. 예를 들어 배열 A의 인덱스 (i,j)의 구간 합을 구한다 하면 0~j까지의 누적 합에서 0~(i-1)의 누적 합을 빼면 된다. 이를 합배열을 사용한 수식으로 표현하면 다음과 같다.
❓합 배열을 사용해서 구간 합을 구하는 것이 왜 효율적일까?
합 배열을 사용하지 않고 구간합을 계산하는 방법은 구간의 모든 원소를 직접 더하는 방법이다. 다만 이는 시간 복잡도가 O(n) 이며 구간의 크기나 구간의 합을 구하는 개수 등이 클수록 연산 시간은 이에 비례하여 늘어난다. 따라서 시간 제한을 고려한다면 적절한 방법이 아니다.
int rangeSum(int[] numbers, int start, int end) { // 구간 합 수동 구
int sum = 0;
for (int i = start; i <= end; i++) { // 시간 복잡도(O(n))
sum += numbers[i];
}
return sum;
}
int result = rangeSum(numbers, 2, 4); // 구간 합을 여러개 구해야 한다면 메서드를 여러 번 실행해야 함
따라서 다음과 같이 합배열을 생성한 후 이미 생성된 합배열의 인덱스를 사용해서 구간 합을 구하는 것이 시간 복잡도 O(1) 로 훨씬 효율적이다.
// 합배열 생성
int[] prefixSum = new int[numbers.length];
prefixSum[0] = numbers[0];
for (int i = 1; i < numbers.length; i++) {
prefixSum[i] = prefixSum[i-1] + numbers[i];
}// 구간 합
int rangeSum(int[] prefixSum, int i, int j) {
if (i == 0) {
return prefixSum[j];
} else {
return prefixSum[j] - prefixSum[i-1]; // 합배열 사용해서 계산 -> 이미 생성된 배열의 요소로 계산 하므로 시간 복잡도O(1)
}
}