안녕하세요! 오늘은 자바 코딩테스트에서 빈번하게 출제되는 알고리즘 중 하나인 구간 합 구하기에 대해 깊이 있게 살펴보려고 합니다. 특히, 이 강좌에서는 구간 합을 구하는 알고리즘 문제를 하나 선정하여 그 풀이 과정을 자세히 설명하겠습니다.
문제 정의
주어진 정수 배열 arr가 있을 때, 여러 쿼리가 주어집니다. 각 쿼리는 두 정수 start와 end를 포함하며, 이 경우 arr[start] + arr[start + 1] + ... + arr[end]를 구하는 문제입니다. 이 문제에서 요구하는 것은 각 쿼리에 대해 구간 합을 효율적으로 계산하는 것입니다.
문제 예시
입력:
arr = [1, 2, 3, 4, 5]
쿼리 = [[0, 2], [1, 3], [2, 4]]
출력:
[6, 9, 12]
풀이 알고리즘
이 문제를 해결하기 위해서는 배열에 대한 여러 번의 구간 합을 효율적으로 처리할 수 있어야 합니다. 기본적으로, 각 쿼리마다 배열의 일부를 반복하여 합산하는 방법은 비효율적일 수 있습니다. 이러한 비효율성을 줄이기 위해 “구간 합 배열”을 활용한 접근 방법을 소개하겠습니다.
구간 합 배열 설명
구간 합 배열(`prefix sum array`)은 주어진 배열의 원소를 누적하여 전처리하는 방법입니다. 이를 통해 각 구간 합을 O(1)의 시간 복잡도 내에 계산할 수 있습니다. 구간 합 배열의 정의는 다음과 같습니다:
prefix[i] = arr[0] + arr[1] + ... + arr[i]
즉, prefixSum[j] - prefixSum[i-1]로 구간 arr[i] ~ arr[j]의 합을 구할 수 있습니다. 여기서 prefixSum[-1]은 0으로 가정합니다.
구현 단계
- 구간 합 배열 생성: 주어진 배열을 이용해 구간 합 배열을 생성합니다.
- 쿼리 처리: 각 쿼리에 대해 구간 합을 O(1) 복잡도로 계산합니다.
자바 코드 구현
public class RangeSum {
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5};
int[][] queries = {{0, 2}, {1, 3}, {2, 4}};
int[] result = rangeSum(arr, queries);
for (int sum : result) {
System.out.println(sum);
}
}
public static int[] rangeSum(int[] arr, int[][] queries) {
int n = arr.length;
int[] prefixSum = new int[n];
prefixSum[0] = arr[0];
// 누적합 배열 생성
for (int i = 1; i < n; i++) {
prefixSum[i] = prefixSum[i - 1] + arr[i];
}
int[] results = new int[queries.length];
for (int i = 0; i < queries.length; i++) {
int start = queries[i][0];
int end = queries[i][1];
// 구간 합 계산
results[i] = (start > 0) ? (prefixSum[end] - prefixSum[start - 1]) : prefixSum[end];
}
return results;
}
}
코드 설명
위의 자바 코드는 사용자 정의 클래스 RangeSum을 만들고, main 메소드에서 배열과 쿼리를 정의합니다. rangeSum 메소드는 주어진 배열로부터 구간 합 배열을 만들어 각 쿼리의 구간 합을 계산하는 기능을 수행합니다.
1. 누적합 배열 생성
먼저 첫 번째 원소를 초기화하고, 반복문을 통해 누적합 배열을 만듭니다. 이 과정은 O(n) 시간 복잡도를 가지며, n은 배열의 길이입니다.
2. 쿼리 처리
각 쿼리에 대해 누적합 배열을 활용하여 O(1)로 구간 합을 계산합니다. 데이터가 많거나 쿼리가 많을 경우 이 방법이 성능상 유리할 것입니다.
복잡도 분석
이 코드의 시간 복잡도는 O(n + m)입니다. 여기서 n은 배열의 길이이고, m은 쿼리의 수입니다. 따라서 초기화 과정에서 O(n)의 시간 복잡도를 소모하고, 각 쿼리에 대해 O(1)를 소모하므로 전체 시간 복잡도는 O(n + m)입니다. 이를 통해 준수한 성능을 보장받을 수 있습니다.
결론
오늘은 자바 코딩테스트에서 구간 합을 구하는 문제를 다루어 보았습니다. 배열의 누적합 배열을 이용하면 여러 쿼리에 대해 효율적으로 구간 합을 계산할 수 있음을 알 수 있었습니다. 실제 코딩테스트에 응용해보면 유용한 알고리즘이므로 꼭 기억해 두시기 바랍니다! 앞으로도 더 많은 알고리즘 문제풀이 강좌를 준비하겠습니다. 감사합니다!