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

안녕하세요! 이번 강좌에서는 자바스크립트 코딩 테스트에서 자주 출제되는 “구간 합” 문제를 심도 있게 다뤄보겠습니다. 구간 합 문제는 주어진 수열에서 임의의 구간의 합을 효율적으로 구하는 문제로, 다양한 최적화 기법을 통해 해결할 수 있습니다. 우리가 다룰 구간 합 문제는 특히 배열의 크기가 클 때 시간이 많이 소요될 수 있기 때문에, 보다 효율적인 알고리즘을 설계하는 것이 중요합니다.

문제 소개

다음은 구간 합에 관한 문제입니다:

문제 설명

정수로 이루어진 배열 arr와 여러 쌍의 정수 (l, r)이 주어집니다. 각 쌍은 구간의 시작점 l과 끝점 r을 나타냅니다. arr[l] + arr[l + 1] + ... + arr[r]의 합을 구하는 프로그램을 작성하시오. 배열의 길이와 쌍의 개수는 다음과 같습니다:

  • 1 ≤ arr.length ≤ 106
  • 1 ≤ l, r ≤ arr.length
  • 0 ≤ arr[i] ≤ 109

예를 들어, 배열 arr = [1, 2, 3, 4, 5]이고, 쌍 (1, 3)이 주어졌다면, 구간 합은 arr[1] + arr[2] + arr[3] = 2 + 3 + 4 = 9입니다.

문제 접근 방법

이 문제를 효율적으로 해결하기 위해서는 단순히 반복문을 통해 각 구간의 합을 계산하는 것은 적절하지 않습니다. 이유는 최악의 경우 O(N * M)의 시간 복잡도를 가지게 되므로, 데이터의 크기가 크면 지수적으로 시간이 늘어날 수 있습니다. 대신에 더 효과적인 접근 방법을 사용할 수 있습니다.

전처리 기법: 누적 합 배열

구간 합 문제를 해결하기 위한 방법 중 하나는 누적 합 배열(Prefix Sum Array)을 만드는 것입니다. 누적 합 배열을 사용하면, 구간의 합을 O(1)로 계산할 수 있습니다. 누적 합 배열의 정의는 다음과 같습니다:

prefix[i] = arr[0] + arr[1] + ... + arr[i-1]

따라서, 구간 (l, r)의 합은 다음과 같이 계산할 수 있습니다:

sum(l, r) = prefix[r + 1] - prefix[l]

이를 통해 각 쌍의 구간 합을 O(1) 시간 안에 구할 수 있습니다. 전체 알고리즘의 시간 복잡도는 O(N + M)이 되며, 여기서 N은 배열의 크기, M은 쌍의 개수입니다.

구현 단계

이제 누적 합 배열을 사용하여 문제를 해결하는 자바스크립트 코드를 구현해보겠습니다.

1단계: 누적 합 배열 생성


function createPrefixSum(arr) {
    const prefix = new Array(arr.length + 1).fill(0);
    for (let i = 0; i < arr.length; i++) {
        prefix[i + 1] = prefix[i] + arr[i];
    }
    return prefix;
}

2단계: 구간 합 계산


function rangeSum(prefix, l, r) {
    return prefix[r + 1] - prefix[l];
}

3단계: 메인 함수 구현


function calculateRangeSums(arr, queries) {
    const prefix = createPrefixSum(arr);
    const results = [];
    for (let [l, r] of queries) {
        results.push(rangeSum(prefix, l - 1, r - 1)); // 1-based to 0-based
    }
    return results;
}

// 예시 사용
const arr = [1, 2, 3, 4, 5];
const queries = [[1, 3], [2, 5], [0, 2]];
const results = calculateRangeSums(arr, queries);
console.log(results); // [9, 14, 6]

결과 분석

위 코드는 주어진 배열과 쿼리를 기반으로 매 쿼리의 구간 합을 효율적으로 계산하여 결과를 출력하는 프로그램입니다. 결과적으로 구간 합을 빠르게 구할 수 있으며, 배열의 크기나 쿼리 개수에 따라 성능이 저하되지 않습니다.

시간 복잡도

본 알고리즘의 시간 복잡도는 다음과 같습니다:

  • 누적 합 배열 생성: O(N)
  • 각 쿼리 처리: O(1) (M개 쿼리 처리 전부 합치면 O(M))

결과적으로 전체 시간 복잡도는 O(N + M)이며, 이는 매우 효율적인 수준입니다.

결론

이제 구간 합 문제를 누적 합 배열을 사용하여 효율적으로 해결하는 방법을 배웠습니다. 코딩 테스트에서 구간 합 문제는 자주 출제되는 주제이므로, 이와 같은 최적화 기법을 이해하고 활용하는 것이 중요합니다. 연습을 통해 다양한 유형의 문제를 해결해 보시기 바랍니다!

추가 연습 문제

다음과 같은 변형 문제를 연습해보세요:

  • 구간 합 대신 구간의 최대값을 구하는 문제
  • 구간의 곱을 구하는 문제 (단, 나누기 연산을 고려해야 할 수도 있음)
  • 다양한 쿼리(예: 구간 증가, 감소 등)가 주어질 때 어떻게 처리할 것인지 고민해보기

위 내용을 바탕으로 다양한 문제를 해결해 보시길 바랍니다. 감사합니다!