문제
주어진 정수 배열 arr와 두 개의 정수 left, right가 있습니다.
이 때, arr[left] + arr[left + 1] + ... + arr[right]의 값을 계산하는 함수를 작성하시오.
단, arr는 1 ≤ arr.length ≤ 100,000의 범위를 가지며,
각 원소는 -10^9 ≤ arr[i] ≤ 10^9까지의 범위를 가집니다.
여러분은 O(log N) 혹은 O(1)의 시간 복잡도로 구간 합을 구할 수 있는 효율적인 방법을 찾는 것을 목표로 합니다.
문제 접근 방법
구간 합 문제는 여러 가지 방법으로 해결할 수 있지만, 효율적인 방법으로는
누적 합(Prefix Sum)을 활용한 접근 방식이 있습니다. 누적 합을 통해 주어진 구간
[left, right]의 합을 O(1)의 시간 복잡도로 계산할 수 있습니다.
기본적인 아이디어는 배열의 각 인덱스까지의 합을 미리 계산하여 저장하는 것입니다.
이를 통해 특정 구간의 합은 다음과 같이 구할 수 있습니다.
sum(left, right) = prefixSum[right] - prefixSum[left - 1]
여기서 prefixSum[i]는 배열의 처음부터 i번째 요소까지의 합입니다.
이 방법은 배열을 한 번 순회하는 O(N)의 복잡도를 가지고 있으며, 이후 각 구간 합은 O(1)로 계산할 수 있습니다.
구현
코드
#include <iostream>
#include <vector>
using namespace std;
class SubarraySum {
public:
SubarraySum(const vector<int>& arr) {
int n = arr.size();
prefixSum.resize(n + 1);
prefixSum[0] = 0; // prefixSum[0]은 0으로 초기화합니다.
for (int i = 1; i <= n; i++) {
prefixSum[i] = prefixSum[i - 1] + arr[i - 1];
}
}
int getSum(int left, int right) {
return prefixSum[right] - prefixSum[left - 1];
}
private:
vector<int> prefixSum; // 누적 합을 저장하는 배열입니다.
};
int main() {
int n; // 배열의 크기
cout << "배열의 크기를 입력하세요: ";
cin >> n;
vector<int> arr(n);
cout << "배열의 원소를 입력하세요: ";
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
SubarraySum subarray(arr);
int left, right;
cout << "구간의 왼쪽 경계를 입력하세요 (1부터 시작): ";
cin >> left;
cout << "구간의 오른쪽 경계를 입력하세요: ";
cin >> right;
int result = subarray.getSum(left, right);
cout << "구간 [" << left << ", " << right << "]의 합은: " << result << endl;
return 0;
}
코드 설명
클래스 정의
SubarraySum 클래스는 구간 합을 계산하는 기능을 제공합니다.
이 클래스의 생성자에서 배치된 배열의 원소를 기반으로 누적 합을 초기화합니다.
배열의 크기를 저장하는 n 변수를 정의하고, prefixSum 배열을(`[0]`을 하나 포함하여) 생성합니다.
누적 합 계산
생성자 내부의 for 루프를 통해 배열을 순회하여
각 인덱스까지의 합을 prefixSum 배열에 저장합니다.
이는 배열의 첫 번째 인덱스부터 시작하기 때문에 배열의 크기보다 1 큰 크기를 가지는 것이 특징입니다.
구간 합 계산
getSum(int left, int right) 메소드는 주어진 left와 right 인덱스를
사용하여 구간 합을 반환합니다. 누적 합 배열의 값을 이용하여 간단히
prefixSum[right] - prefixSum[left - 1] 로 구간 합을 계산할 수 있습니다.
테스트 및 활용
본 코드를 통해 사용자는 구간의 왼쪽과 오른쪽 경계를 입력받고,
해당 구간의 합을 쉽게 계산할 수 있습니다. 이 알고리즘은 입력 배열의 크기가 커져도
매끄럽게 동작하며, 구간 합을 O(1)의 시간 복잡도로 신속하게 처리할 수 있는 장점을 가집니다.
결론
구간 합 문제는 다양한 응용 프로그램에서도 널리 사용되며,
이러한 누적 합 방식은 데이터 분석, 통계 처리 등 여러 분야에서 유용성을 보여줍니다.
이 간단하지만 뛰어난 방법을 통해 문제 해결의 효율성을 높일 수 있습니다.
이 강좌가 여러분의 C++ 코딩 테스트 준비에 도움이 되길 바랍니다!