저자: 조광형
작성일: 2024년 11월 26일
1. 문제 설명
이번 시간에는 구간 합 문제를 다뤄 보겠습니다. 알고리즘 및 코딩 테스트에서 자주 접할 수 있는 문제 중 하나로, 주어진 배열의 특정 구간의 합을 효율적으로 계산하는 방법을 배워보겠습니다.
문제는 다음과 같습니다.
정수로 이루어진 배열 A와 다양한 쿼리들이 주어질 때, 각 쿼리에서 제시한 구간 l, r에 대하여 A[l] 부터 A[r] 까지의 합을 구하시오.
입력 형식:
- 배열 A의 크기 N (1 ≤ N ≤ 100,000)
- 배열 A의 원소 (1 ≤ A[i] ≤ 100,000)
- 쿼리의 개수 Q (1 ≤ Q ≤ 100,000)
- 각 쿼리는 두 개의 정수 l, r를 포함하며 (1 ≤ l ≤ r ≤ N).
출력 형식:
각 쿼리에 대한 구간 합을 출력하시오.
2. 접근 방법
문제의 접근 방법은 두 가지로 나눌 수 있습니다:
- 단순하게 반복문을 사용하여 합계를 계산하는 방법 (비효율적)
- 누적 합 배열을 사용하여 O(1) 시간 내에 구간 합을 구하는 방법 (효율적)
첫 번째 접근 방법의 경우, 각 쿼리에 대해 구간의 합을 직접 계산하면 시간 복잡도가 쿼리 개수 Q와 배열 크기 N의 곱이 되어 O(N * Q)입니다. 이 경우, 최악의 경우 1010번의 연산이 필요해 효율적이지 않습니다.
두 번째 접근 방법은 누적 합 배열을 생성하여 O(1) 시간 내에 구간 합을 구하는 것입니다. 이 방법의 전체적인 접근 방식은 다음과 같습니다:
- 우선 N 크기의 누적 합 배열을 생성합니다.
- 누적 합 배열의 i번 인덱스에는 A[0]부터 A[i]까지의 합이 저장됩니다.
- 각 쿼리 (l, r)의 합은 누적 합 배열을 이용하여 S[r] – S[l-1]로 계산할 수 있습니다.
3. 코드 구현
public class IntervalSum {
public static void main(String[] args) {
int N = 5; // 배열 크기
int[] A = {1, 2, 3, 4, 5}; // 입력 값
int Q = 3; // 쿼리 수
int[][] queries = {{1, 3}, {2, 5}, {1, 5}}; // 쿼리 예시
// 누적 합 배열 생성
long[] prefixSum = new long[N + 1];
for (int i = 1; i <= N; i++) {
prefixSum[i] = prefixSum[i - 1] + A[i - 1];
}
// 각 쿼리 처리
for (int i = 0; i < Q; i++) {
int l = queries[i][0];
int r = queries[i][1];
long sum = prefixSum[r] - prefixSum[l - 1];
System.out.println("Sum from " + l + " to " + r + ": " + sum);
}
}
}
4. 코드 설명
위 코드는 다음과 같은 절차로 동작합니다:
- 배열 A와 쿼리 개수 Q, 각 쿼리의 l, r을 입력받습니다.
- 우선 누적 합 배열을 생성합니다. 이 배열의 i번 인덱스에는 배열 A의 0번 인덱스부터 i-1 인덱스까지의 합이 저장됩니다.
- 각 쿼리를 처리할 때, 해당하는 구간의 합은 prefixSum[r] – prefixSum[l-1]으로 계산하여 출력합니다.
5. 시간 복잡도 분석
이 알고리즘의 시간 복잡도는 다음과 같습니다:
- 누적 합 배열을 생성하는 데 O(N) 시간이 소요됩니다.
- 각 쿼리를 처리하는 데 O(1) 시간이 소요됩니다.
따라서 전체 시간 복잡도는 O(N + Q)입니다. 이는 매우 효율적인 방법으로, 배열의 크기와 쿼리의 개수가 모두 최대값인 경우에도 빠른 성능을 보입니다.
6. 마지막 정리
구간 합 구하기 문제는 알고리즘 및 데이터 구조를 이해하는 데 중요한 개념입니다. 이번 강좌에서는 누적 합 배열을 이용한 효율적인 구간 합 계산 방법을 배웠습니다. 이 방법을 통해 많은 양의 데이터를 처리할 때 성능을 극대화할 수 있습니다.
이러한 종류의 문제는 또한 다양한 변형 문제로 접할 수 있으므로 추가적으로 연습하는 것이 중요합니다. 앞으로도 다양한 알고리즘 문제를 풀어보며 더욱 깊고 넓은 이해를 쌓아 나가길 바랍니다.