알고리즘 - 4. 누적 합

algorithmsarraysoptimizationprefix-sumsrange-queries
By sko9/29/20252 min read

누적 합을 사용해야 하는 경우

배열에서 범위에 대한 누적 속성을 반복적으로 쿼리해야 할 때 누적 합을 사용합니다. 가장 일반적으로 범위 합에 사용되지만 다음과 같이 응용할 수 있습니다:

  • 범위 합 쿼리 (고전적인 사용 사례)
  • 부분 배열 합 문제 (목표 합을 가진 부분 배열 찾기)
  • 누적 빈도 (범위 내 요소 개수 세기)
  • 범위 곱 (로그 또는 별도 배열을 사용한 수정으로)
  • 2D 행렬 영역 합 (2D 누적 합으로 확장)
  • 차분 배열 (범위 업데이트를 효율적으로 적용)
  • 구간에 대한 누적 속성의 여러 쿼리가 필요한 문제

예제 문제

일일 매출 분석: 일일 매출 데이터 [3, 5, 2, 8, 4, 6, 1]이 주어지고, 다양한 날짜 범위에 대한 매출에 관한 여러 쿼리에 답해야 합니다.

  • 쿼리: "2일차부터 5일차까지의 총 매출은?"
  • 쿼리: "0일차부터 3일차까지의 총 매출은?"
  • 쿼리: "4일차부터 6일차까지의 총 매출은?"

: 누적 합 배열을 한 번 구축하면 각 쿼리를 O(1) 시간에 답할 수 있습니다. 2일차부터 5일차까지: 합은 20 (2 + 8 + 4 + 6)입니다.

가장 중요한 핵심

모든 범위 합은 두 누적 합의 차이와 같습니다 - 시작부터의 누적 합을 미리 계산함으로써 뺄셈을 사용하여 모든 부분 배열 합을 즉시 계산할 수 있습니다: sum(i, j) = prefix[j] - prefix[i-1].

참고: 이 알고리즘의 힘은 문제의 변환에 있습니다. 요소를 반복적으로 합산하는 대신(쿼리당 O(n)), 모든 부분 합을 한 번만 미리 계산합니다. 쿼리 시점에는 "오른쪽 경계까지의 합계"에서 "왼쪽 경계 이전의 합계"를 빼기만 하면 됩니다. 이렇게 반복적인 O(n) 연산이 O(1) 조회로 변환됩니다.

왜 "누적 합(Prefix Sum)"인가?: 이 이름은 배열의 각 접두사(시작 부분)의 을 저장하는 것에서 유래합니다. 배열 [3, 5, 2, 8]의 경우, 접두사는 [3], [3, 5], [3, 5, 2], [3, 5, 2, 8]입니다. 그 합을 저장합니다: [0, 3, 8, 10, 18]. 이 기법이 "Prefix Sum"이라고 불리는 이유는 고전적인 사용 사례가 덧셈이기 때문입니다—동일한 패턴이 다른 연산(누적 곱 등)에도 작동하지만, 덜 일반적입니다.

항등원이 중요합니다: 초기값은 연산에 따라 다릅니다: 덧셈의 경우 0 (x + 0 = x이므로), 곱셈의 경우 1 (x × 1 = x이므로). 누적 곱의 경우 prefix[0] = 1을 사용하고 역연산(나눗셈)을 사용하여 범위를 추출합니다: product(left, right) = prefix[right+1] / prefix[left]. 이것은 뺄셈이 덧셈의 역연산인 것과 유사합니다.

의사결정 프레임워크

누적 합 기법은 두 단계로 구성됩니다:

구축 단계: 배열을 한 번 순회하면서 연산(덧셈, 곱셈 등)을 사용하여 값을 누적

쿼리 단계: 임의의 범위 [left, right]에 대해 두 개의 미리 계산된 값에 역연산을 사용하여 범위 결과를 추출

  • 덧셈 → 뺄셈: sum(left, right) = prefix[right+1] - prefix[left]
  • 곱셈 → 나눗셈: product(left, right) = prefix[right+1] / prefix[left]
  • 최댓값 → 최댓값 (멱등): max(left, right) = max(prefix[right+1], -prefix[left]) (세그먼트 트리 같은 다른 접근법 필요)

코드

// 구축 단계: 모든 누적 합을 미리 계산
function buildPrefixSum(nums) {
  // 빈 접두사를 나타내는 0으로 시작
  const prefix = new Array(nums.length + 1).fill(0);

  for (let i = 0; i < nums.length; i++) {
    const currentNum = nums[i];
    const sumSoFar = prefix[i];

    // 의사결정 프레임워크: 누적 합계를 축적
    prefix[i + 1] = sumSoFar + currentNum;
  }

  return prefix;
}

// 쿼리 단계: 역연산을 사용하여 범위 추출
function rangeSum(prefix, left, right) {
  const totalUpToRight = prefix[right + 1];
  const totalBeforeLeft = prefix[left];

  // 의사결정 프레임워크: 뺄셈으로 범위 추출
  return totalUpToRight - totalBeforeLeft;
}

// 일일 매출 데이터 사용 예제
const dailySales = [3, 5, 2, 8, 4, 6, 1];
const prefixSums = buildPrefixSum(dailySales);

console.log(rangeSum(prefixSums, 2, 5)); // 20 (2~5일차: 2+8+4+6)
console.log(rangeSum(prefixSums, 0, 3)); // 18 (0~3일차: 3+5+2+8)
console.log(rangeSum(prefixSums, 4, 6)); // 11 (4~6일차: 4+6+1)

의문 해소

흔한 의문: "왜 누적 합 배열의 시작 부분에 추가 요소를 넣나요? 원래 배열과 동일한 인덱스를 사용할 수 없나요?"

추가 요소를 피하고 싶은 이유

일대일 대응 관계가 더 직관적으로 보입니다:

  • 원래 배열: [3, 5, 2, 8, 4, 6, 1]
  • 누적 합 배열: [3, 8, 10, 18, 22, 28, 29] (같은 길이)

이 방법에서는 prefix[i]가 0부터 i까지 요소의 합이 되어 자연스럽게 느껴집니다.

추가 요소가 중요한 이유

핵심 깨달음: 추가 요소가 없으면 인덱스 0에서 시작하는 범위에 대해 특수 케이스 처리가 필요합니다!

추가 요소가 없을 때 무슨 일이 일어나는지 봅시다:

원래 배열:  [3, 5, 2, 8, 4, 6, 1]
누적 합:     [3, 8, 10, 18, 22, 28, 29]

쿼리 sum(2, 5):
  = prefix[5] - prefix[1]
  = 28 - 8
  = 20 ✓ (정답: 2+8+4+6)

쿼리 sum(0, 3):
  = prefix[3] - prefix[-1]  // 앗! 인덱스 -1은 존재하지 않음
  = prefix[3] - ???
  = 특수 케이스 필요: if (left == 0) return prefix[right]

우아한 해결책: prefix[0] = 0

시작 부분에 0을 추가함으로써:

원래 배열:  [3, 5, 2, 8, 4, 6, 1]
누적 합:     [0, 3, 8, 10, 18, 22, 28, 29]

            "0개 요소의 합"을 나타냄

쿼리 sum(0, 3):
  = prefix[4] - prefix[0]
  = 18 - 0
  = 18 ✓ (정답: 3+5+2+8)

이 패턴이 정확성을 보장하는 이유

공식 sum(left, right) = prefix[right+1] - prefix[left]이 보편적으로 작동하는 이유:

  1. prefix[i] = 처음 i개 요소의 합 (인덱스 i의 요소는 포함하지 않음)
  2. prefix[right+1] = 인덱스 right까지의 모든 요소의 합 (right 포함)
  3. prefix[left] = 인덱스 left 이전의 모든 요소의 합
  4. 그 차이가 범위 [left, right]의 요소를 정확히 제공

이것은 모든 특수 케이스를 제거하고 코드를 더 깔끔하고, 유지보수하기 쉽고, 오류가 발생하기 어렵게 만듭니다. 추가 메모리 비용(1개 요소)은 얻는 명확성에 비하면 무시할 수 있습니다.