2023년 10월 5일
1. 문제 소개
구간 합 구하기 3 문제는 알고리즘 문제 해결 과정에서 자주 접하게 되는 문제 유형으로, 특히나 많은 데이터의 합을 계산할 때 효율성을 보여줍니다.
이 문제는 특정 구간의 합을 query를 통해 빠르게 구할 수 있는 방법에 대해 다룹니다.
구간 합을 알고리즘으로 계산하는 것은 특히 데이터베이스와 관련된 문제에서 매우 유용합니다.
오늘 우리는 이 문제를 해결하기 위해 여러 기법을 분석하고, 자바스크립트를 사용하여 해결해 보겠습니다.
2. 문제 설명
주어진 배열 A가 있으며, A의 길이는 N입니다. 양의 정수 쿼리 M이 주어질 때,
각 쿼리는 두 개의 정수 i와 j로 구성되어 있으며, 이 때 A[i] + A[i+1] + ... + A[j]의 값을
구해야 합니다. 쿼리는 최대 100,000개까지 존재할 수 있으며, A의 각 수는 최대 1,000,000입니다.
즉, 우리는 주어진 A 배열과 쿼리들을 기반으로 하여 각 구간의 합을 효율적으로 계산해야 합니다.
3. 문제 해결 전략
구간 합 문제를 해결하기 위해 우리는 두 가지 주요 방법을 사용할 것입니다.
– 첫째, 기본적인 방법인 이중 반복문을 사용하여 각 쿼리마다 합을 계산하는 방법입니다.
– 둘째, 구간 합을 미리 계산해 두고 쿼리 시 빠르게 결과를 도출하는 방법입니다.
특히, 두 번째 방법은 O(N)의 전처리를 통해 O(1) 시간으로 쿼리 결과를 얻을 수 있습니다.
따라서 우리가 이 문제를 더욱 효율적으로 해결하는 데 도움을 줄 것입니다.
4. 기본 방법 (O(N) x M)
이 방법은 매우 직관적이지만, 시간 복잡도는 O(N * M)입니다.
이 방식의 코드 구현은 다음과 같습니다.
function simpleRangeSum(A, queries) {
const results = [];
for (let [i, j] of queries) {
let sum = 0;
for (let k = i; k <= j; k++) {
sum += A[k];
}
results.push(sum);
}
return results;
}
이 코드는 각 쿼리마다 해당 인덱스의 합을 반복하여 계산합니다. 그러나 문제의 제한 조건에서
이 방법은 비효율적입니다. 따라서 우리는 보다 효율적인 방법으로 넘어가야 합니다.
5. 효율적인 방법 (O(N) + O(1) per Query)
효율적인 방법을 살펴보면 먼저, 원본 배열의 구간 합을 저장할 배열을 만듭니다.
먼저, 구간 합 배열을 만드는 과정이 필요합니다. 구간 합 배열을 만들면,
각 쿼리의 결과는 단순히 두 쿼리 누적 합의 차로 얻을 수 있습니다.
function prefixSum(A) {
const prefix = new Array(A.length + 1).fill(0);
for (let i = 0; i < A.length; i++) {
prefix[i + 1] = prefix[i] + A[i];
}
return prefix;
}
function rangeSum(A, queries) {
const prefix = prefixSum(A);
const results = [];
for (let [i, j] of queries) {
results.push(prefix[j + 1] - prefix[i]);
}
return results;
}
위의 구현에서, prefixSum 함수는 전체 데이터에 대한 누적 합을 계산하여 prefix 배열에 저장합니다.
이후에 각 쿼리는 O(1) 시간에 구간 합을 도출해낼 수 있습니다. 이 방식은
O(N) + O(1)로 쿼리를 처리할 수 있으므로 매우 효율적입니다.
6. 코드 설명
위의 코드를 분석하면 먼저 prefixSum 함수에서
배열의 길이에 하나를 더한 빈 배열을 만들고,
이 배열의 각 인덱스에 대한 누적 합을 계산합니다. 이 누적 합 배열을 통해
rangeSum 함수는 주어진 쿼리로부터 시작 인덱스 i와 종료 인덱스 j를 받아
빠르게 구간 합을 계산합니다.
이제 주어진 쿼리 수가 많을 때 시간 복잡도를 고려해야 하는데,
바로 위 솔루션이 시간 복잡도 면에서 매우 효율적이기 때문입니다.
각 쿼리를 처리하는 과정에서 불필요한 반복문이 키가 되었으며,
이 과정을 통해 결과를 도출함으로써 성능 개선이 이루어졌습니다.
7. 예제 테스트
다음과 같은 예제를 통해 위의 코드를 테스트해 보겠습니다.
배열 A = [1, 2, 3, 4, 5]이고, 쿼리는
[[0, 2], [1, 3], [2, 4]]입니다.
const A = [1, 2, 3, 4, 5];
const queries = [[0, 2], [1, 3], [2, 4]];
const results = rangeSum(A, queries);
console.log(results); // [6, 9, 12]
위의 테스트 결과는 각 쿼리에 대해 올바른 누적 합을 도출하고 있습니다. 테스팅 과정을 통해 우리의 코드가 정확하게 작동하는
지를 확인할 수 있으며, 이는 정답을 보장하는 중요한 과정입니다.
8. 마무리
구간 합 구하기 3는 다양한 알고리즘 문제 해결 스킬을 보여주는 훌륭한 예제입니다.
선수치기를 통해 구간 합 문제를 해결하는 것은 실제로도 일상적인 데이터 처리 작업에 많이 사용되고 있습니다.
오늘 배운 내용을 바탕으로 여러분도 비슷한 문제를 해결할 수 있는 능력을 기르셨길 바라며,
문제가 주어졌을 때 알고리즘을 어떻게 구성할지에 대한 통찰을 얻으셨기를 바랍니다.
자바스크립트를 통한 문제 해결 경험을 지속해서 쌓아가시기를 바랍니다.