자바스크립트 코딩테스트 강좌, 구간 합 구하기 2

문제 설명

구간 합 문제는 알고리즘 문제에서 자주 등장하는 유형 중 하나입니다. 이번 강좌에서는 구간 합을 계산하는 두 번째 문제를 다룹니다. 주어진 배열에서 두 점의 구간 합을 효율적으로 계산하는 방법에 대해 배우겠습니다.

문제:
정수 배열 A와 쿼리 배열 queries가 주어질 때, 각 쿼리 (l, r)에 대해 배열 A의 l 번째부터 r 번째까지의 구간 합을 계산하시오.

배열의 인덱스는 0부터 시작하며, 배열의 크기는 N이고 쿼리의 개수는 Q입니다.

입력 형식

1. 첫 번째 줄에 배열 A의 크기 N (1 ≤ N ≤ 10⁶)이 주어진다.

2. 두 번째 줄에 배열 A의 원소들이 주어진다. (A[i]는 정수, -10⁹ ≤ A[i] ≤ 10⁹)

3. 세 번째 줄에 쿼리의 개수 Q (1 ≤ Q ≤ 10⁵)가 주어진다.

4. 다음 Q줄에는 각 쿼리 (l, r)이 주어진다. (0 ≤ l ≤ r < N)

출력 형식

각 쿼리마다 구간 합을 한 줄에 하나씩 출력한다.

예제

풀이 과정

구간 합을 효율적으로 구하기 위한 첫 번째 단계는 전치합 (prefix sum) 배열을 만드는 것입니다. 전치합 배열은 배열의 각 인덱스까지의 원소들의 합을 저장하는 배열로, 이를 이용하면 구간 합을 O(1) 시간에 계산할 수 있습니다.

전치합 배열 만들기

전치합 배열 prefix는 다음과 같이 정의합니다:

prefix[0] = A[0],

prefix[i] = prefix[i-1] + A[i] (for 1 ≤ i < N)

이렇게 전치합 배열을 만들면, 구간 합 A[l] + ... + A[r]는 다음과 같이 구할 수 있습니다:

sum(l, r) = prefix[r] - prefix[l - 1] (단, l > 0)

위의 경우, l = 0일 때는 sum(0, r) = prefix[r]로 처리합니다.

구현

이제 전치합 배열을 만들고, 각 쿼리에 대해 구간 합을 계산하는 코드를 작성해보겠습니다. 아래는 자바스크립트로 구현한 코드입니다:

    
    function rangeSum(A, queries) {
        const N = A.length;
        const prefix = new Array(N);
        prefix[0] = A[0];
        
        // 전치합 배열 생성
        for (let i = 1; i < N; i++) {
            prefix[i] = prefix[i - 1] + A[i];
        }

        const result = [];
        // 쿼리 처리
        for (const [l, r] of queries) {
            if (l === 0) {
                result.push(prefix[r]);
            } else {
                result.push(prefix[r] - prefix[l - 1]);
            }
        }

        return result;
    }

    // 예제 입력
    const A = [1, 2, 3, 4, 5];
    const queries = [[0, 2], [1, 4], [2, 2]];
    console.log(rangeSum(A, queries)); // [6, 14, 3]

시간 복잡도 분석

전치합 배열을 만드는 과정은 O(N) 시간이 소요되며, 각 쿼리의 시간을 O(1)로 처리할 수 있습니다. 따라서 전체 알고리즘의 시간 복잡도는 O(N + Q)입니다. 이는 주어진 문제의 입력 조건을 만족하는 효율적인 솔루션입니다.

결론

이번 강좌에서는 구간 합을 구하는 방법에 대해 알아보았습니다. 문제를 해결하기 위해 전치합 배열을 활용하여 O(1) 시간에 구간 합을 계산할 수 있는 방법을 배웠습니다. 이러한 접근 방식은 다른 비슷한 문제를 해결하는 데에도 적용할 수 있으므로, 알고리즘 공부에 많은 도움이 될 것입니다.