누적 합 — 알고리즘 · 오승의 기술블로그

앞에서부터 더해 온 합을 칸 사이마다 적어 두면, 어떤 연속 구간의 합이든 두 값의 차 한 번으로 구할 수 있습니다.

언제 쓰나

배열에서 연속된 구간의 합을 여러 번 다뤄야 할 때 씁니다. 구간 하나의 합을 매번 처음부터 더하면 구간 길이만큼 덧셈이 필요한데, 누적 합을 한 번 만들어 두면 어떤 구간이든 뺄셈 한 번으로 끝납니다.

여러 구간의 합을 반복해서 물어봅니다.
합이 특정 값 k인 구간이 몇 개인지 셉니다. 이때는 누적 합에 Map을 함께 씁니다. 원소가 모두 양수라면 구간을 늘렸다 줄였다 하는 투 포인터로도 풀 수 있지만, 음수가 섞이면 칸을 더해도 합이 커진다는 보장이 없어 투 포인터가 통하지 않습니다. 아래 대표 문제가 이 경우입니다.

어떻게 동작하나

칸 사이에 합을 적어 둔다

nums = [1, 2, 3, -2]의 칸 사이마다, 그 자리까지 더해 온 합을 적어 보겠습니다. 첫 칸 앞에는 아직 아무것도 더하지 않았으니 0을 적습니다. 아래 그림에서 위 줄이 nums의 칸이고, 아래 줄의 동그라미가 칸 사이마다 적은 합입니다.

칸 사이의 이 자리들을 기둥이라고 부르겠습니다. 동그라미 위의 작은 숫자가 기둥 번호입니다. 기둥 j에 적힌 값은 앞에서부터 j칸을 더한 합이고, 이것을 누적 합(prefix sum)이라고 합니다. 코드에서는 보통 prefix[j]로 씁니다.

연속 구간은 두 기둥 사이에 있는 칸들입니다. 그림에서 칠한 [3, -2]는 기둥 2와 기둥 4 사이에 있고, 그 합은 오른쪽 기둥 값에서 왼쪽 기둥 값을 뺀 4 − 3 = 1입니다. 기둥 2까지 더한 값을 기둥 4까지 더한 값에서 빼면, 두 기둥 사이의 칸만 남기 때문입니다. 식으로 쓰면 nums[i]부터 nums[j-1]까지의 합이 prefix[j] - prefix[i]입니다.

기둥 번호와 칸 번호는 하나씩 어긋나 있습니다. 기둥 j는 j번째 칸 nums[j-1]의 뒤에 서 있습니다. 이 어긋남 때문에 구간을 읽을 때 헷갈리기 쉬워서, 그림에서도 칸과 기둥을 위아래 두 줄로 나눠 그렸습니다. 아래 단계별 시각화도 같은 그림입니다.

합이 k인 구간 세기

구간 합을 구하던 식을 거꾸로 쓰면 합이 k인 구간을 셀 수 있습니다. 기둥 j에 서 있을 때 여기서 끝나는 구간의 합이 k가 되려면, 왼쪽 끝 기둥의 값이 prefix[j] - k여야 합니다. 그러니 앞에서 지나온 기둥 중에 값이 prefix[j] - k였던 기둥이 몇 개인지 알면, 기둥 j에서 끝나는 답의 개수를 바로 알 수 있습니다.

지나온 기둥을 매번 다시 훑으면 느리기 때문에, 기둥을 지날 때마다 “이 값을 몇 번 봤는지”를 Map에 적어 둡니다. 그러면 prefix[j] - k를 Map에서 한 번 찾는 것으로 개수가 나옵니다.

nums = [1, 2, 3], k = 3(LeetCode 560의 예제 2)로 해 보면 이렇습니다.

기둥 1(합 1): 1 − 3 = −2. 값이 −2인 기둥은 없습니다.
기둥 2(합 3): 3 − 3 = 0. 기둥 0이 짝이 되고, 그 사이의 [1, 2]가 답입니다.
기둥 3(합 6): 6 − 3 = 3. 기둥 2가 짝이 되고, 그 사이의 [3]이 답입니다.

2단계에서 짝이 된 기둥 0은 아무것도 더하지 않은 첫 칸 앞자리입니다. 그래서 Map은 비워 두지 않고 {0: 1}로, 즉 “값 0인 기둥을 한 번 지나왔다”는 기록을 넣고 시작합니다. 이 기록이 없으면 [1, 2]처럼 첫 칸부터 시작하는 구간을 셀 수 없습니다.

직접 따라가 보기

아래는 조금 더 긴 nums = [1, 2, 3, -2, 2, 1, 2], k = 3입니다. 한 기둥마다 “짝 찾기”와 “Map에 적기” 두 단계로 나눠 진행합니다. 4번째 단계에서 기둥 0과 기둥 2가 호로 이어지며 [1, 2]가 칠해지는 것부터 보세요. 11번째 단계에서는 누적 합 6이 두 번째로 나와 Map의 횟수가 2가 되고, 14번째 단계에서 그 두 기둥이 한꺼번에 짝이 됩니다.

단계 1 / 15

변수

prefix: 0
prefix - k: –
count
result: 0

아직 한 칸도 더하지 않은 기둥 0에서 시작합니다. 누적 합 0을 Map에 1번으로 적어 둡니다

지금 선 기둥
이번에 찾은 구간과 짝 기둥
지나온 기둥
아직 안 간 기둥

앞 세 칸은 LeetCode 560 예제 2(nums = [1, 2, 3], k = 3 → 2)와 같습니다. 빌드할 때 풀이를 실제로 돌려 기록한 단계입니다.

위쪽에서 “빈 Map으로 시작”을 고르면 {0: 1} 없이 같은 풀이가 실행됩니다. 4번째 단계에서 기둥 0과의 짝을 찾지 못해 [1, 2]를 놓치고, 결과는 7이 아니라 6으로 끝납니다.

대표 문제 풀이

LeetCode 560은 정수 배열 nums와 정수 k를 받아, 합이 k인 연속 구간의 개수를 돌려주는 문제입니다. nums = [1, 2, 3], k = 3이면 [1, 2]와 [3] 두 개라서 2를 돌려줍니다.

var subarraySum = function (nums, k) {
  const count = new Map([[0, 1]]); // 기둥 0: 아직 아무것도 더하지 않은 자리
  let prefix = 0; // 지금 서 있는 기둥의 누적 합
  let result = 0;

  for (const num of nums) {
    prefix += num; // 다음 기둥으로 이동

    // ① 값이 prefix - k였던 앞 기둥 수만큼, 여기서 끝나는 구간이 있다
    result += count.get(prefix - k) ?? 0;

    // ② 이번 기둥을 Map에 기록
    count.set(prefix, (count.get(prefix) ?? 0) + 1);
  }

  return result;
};

prefix 배열을 따로 만들지 않고 변수 하나로 걸어가는 것은, 지나간 기둥의 값은 Map에 횟수로만 남아 있으면 충분하기 때문입니다.

①과 ②의 순서는 바꾸면 안 됩니다. ②를 먼저 하면 지금 기둥이 Map에 들어간 뒤에 찾게 되어, k가 0일 때 지금 기둥이 자기 자신과 짝이 되어 칸이 하나도 없는 구간까지 세어 버립니다.

배열을 한 번 지나가고 Map 조회와 기록이 각각 O(1)이므로 시간은 O(n)입니다. Map에는 기둥 값이 최대 n + 1개 들어가므로 공간도 O(n)입니다.

자주 하는 실수

기둥 번호와 칸 번호를 섞습니다. 저는 nums = [1, 2, 1], k = 3으로 연습할 때 기둥 3(누적 합 4)에서 끝나는 구간을 찾으면서, prefix - 3이라는 식까지는 세웠지만 구간을 nums[3]이라고 답했습니다. 길이가 3인 배열에 nums[3]은 없습니다. 4 − 3 = 1이니 짝은 누적 합이 1인 기둥 1이고, 답은 기둥 1과 기둥 3 사이의 칸 [2, 1]이었습니다. 기둥 j는 칸 nums[j-1]의 뒤에 있다는 점을 먼저 떠올리면 구간을 바로 읽을 수 있습니다.

Map을 빈 채로 시작합니다. 첫 칸부터 시작하는 구간은 왼쪽 끝이 기둥 0인데, 기둥 0을 Map에 넣지 않으면 이 구간들을 모두 놓칩니다. 위 시각화의 “빈 Map으로 시작”이 이 경우입니다.