문제 소개
이 글에서는 크기가 n인 정수 배열이 주어졌을 때, 인덱스 L부터 R까지의 요소 합을 구하는 쿼리를 여러 번 처리하는 방법을 알아봅니다. 즉, [L, R] 범위의 합을 반복적으로 계산해야 하는 상황입니다. 예시는 다음과 같습니다.
입력 : arr[] = {1, 2, 3, 4, 5}
L = 1, R = 3
L = 2, R = 4
출력 : 9
12
입력 : arr[] = {1, 2, 3, 4, 5}
L = 0, R = 4
L = 1, R = 2
출력 : 15
5
해결 접근 방식
이 문제를 해결하는 방법은 두 가지가 있습니다. 첫 번째는 브루트 포스(Brute Force) 방식이고, 두 번째는 접두사 합(Prefix Sum)을 이용한 효율적인 방식입니다.
브루트 포스 접근법
가장 직관적인 방법으로, 쿼리마다 주어진 범위를 처음부터 끝까지 순회하면서 합을 계산하고 출력합니다.
예제 코드
#include<bits/stdc++.h>
using namespace std;
int main() {
int arr[] = {1, 2, 3, 4, 5};
int n = sizeof(arr)/sizeof(int); // 주어진 배열의 크기
int L1 = 1, R1 = 3;
int L2 = 2, R2 = 4;
int sum = 0;
for(int i = L1; i <= R1; i++) // 첫 번째 범위 순회
sum += arr[i];
cout << sum << "\n";
sum = 0;
for(int i = L2; i <= R2; i++) // 두 번째 범위 순회
sum += arr[i];
cout << sum << "\n";
}
실행 결과
9 12
코드 설명
이 방식은 단순히 주어진 범위를 순회하며 합을 더합니다. 쿼리가 하나뿐이라면 탐색 시간 복잡도가 O(N)(N은 배열의 크기)이므로 충분히 괜찮습니다. 하지만 쿼리가 Q개 주어지면 전체 시간 복잡도는 O(N×Q)가 됩니다. 안타깝게도 이 정도의 복잡도로는 제약 조건이 큰 문제를 감당할 수 없으므로, 더 높은 제약 조건에서도 동작하는 효율적인 방법을 살펴보겠습니다.
효율적인 접근법: 접두사 합
이 방식에서는 접두사 합을 저장할 새로운 배열 prefix를 만듭니다. prefix[i]에는 인덱스 0부터 i까지의 누적 합이 저장되며, 이후 각 쿼리는 이 배열만으로 즉시 답을 구할 수 있습니다.
예제 코드
#include<bits/stdc++.h>
using namespace std;
int main() {
int arr[] = {1, 2, 3, 4, 5};
int n = sizeof(arr)/sizeof(int); // 주어진 배열의 크기
int L1 = 1, R1 = 3;
int L2 = 2, R2 = 4;
int sum = 0;
int prefix[n];
for(int i = 0; i < n; i++){
sum += arr[i];
prefix[i] = sum;
}
if(L1) // 세그먼테이션 오류 방지
cout << prefix[R1] - prefix[L1 - 1] << "\n";
else
cout << prefix[R1] << "\n";
if(L2) // 세그먼테이션 오류 방지
cout << prefix[R2] - prefix[L2 - 1] << "\n";
else
cout << prefix[R2] << "\n";
}
실행 결과
9 12
코드 설명
누적 합 값을 prefix 배열에 미리 저장해 둡니다. 이렇게 하면 각 범위의 합을 prefix[R] - prefix[L-1]이라는 한 번의 연산으로 구할 수 있어 탐색 시간 복잡도가 O(1)이 됩니다. 이것이 가능한 최선의 복잡도이며, 따라서 Q개의 쿼리가 주어져도 전체 시간 복잡도는 O(N + Q)로, 쿼리 처리 자체는 O(Q)에 수렴합니다. 참고로 L이 0일 때는 L-1 인덱스 접근으로 인한 세그먼테이션 오류를 피하기 위해 분기 처리를 해주었습니다.
마무리 및 확장
이 글에서는 접두사 합 배열을 활용해 업데이트가 없는 범위 합 쿼리 문제를 해결했습니다. 일반적인 브루트 포스 방식과 효율적인 접두사 합 방식을 모두 살펴보았으며, 같은 로직은 C, Java, Python 등 다른 언어로도 손쉽게 작성할 수 있습니다. 만약 배열 값의 업데이트가 함께 발생하는 상황이라면 펜윅 트리(Fenwick Tree)나 세그먼트 트리를 사용하는 것이 좋습니다. 이 글이 도움이 되었기를 바랍니다.