{ }codelper

배우기 › Python

알고리즘 · 29

누적 합과 두 포인터

구간의 합을 뺄셈 한 번으로 구하고, 두 자리를 앞으로만 옮기며 구간을 찾아요.

누적 합은 앞에서부터 더해 온 값을 표로 적어 두는 거예요.
두 포인터는 목록 위의 두 자리를 옮겨 가며 답을 찾는 방법이에요.
아래 예제는 수 6개에서 "l번째부터 r번째까지의 합" 질문 3개에 답하고, 합이 16 이상인 가장 짧은 이어진 구간의 길이를 구해요.

n, q, s = map(int, input().split())a = list(map(int, input().split())) # prefix[i] = 앞에서 i개의 합 (prefix[0] = 0)prefix = [0] * (n + 1)for i in range(n):    prefix[i + 1] = prefix[i] + a[i] for _ in range(q):    l, r = map(int, input().split())    print(prefix[r] - prefix[l - 1])  # l번째부터 r번째까지의 합 # 합이 s 이상인 가장 짧은 이어진 구간: left와 right는 앞으로만 간다best = 0left = 0window = 0for right in range(n):    window += a[right]    while window >= s:        if best == 0 or right - left + 1 < best:            best = right - left + 1        window -= a[left]        left += 1print(best)
stdin
6 3 16
5 1 9 2 7 4
1 6
2 4
3 3
stdout
28
12
9
3

핵심

  • 질문마다 처음부터 다시 더하면 같은 덧셈을 되풀이해요.
    그래서 prefix[i]에 "앞에서 i개의 합"을 미리 적어 둬요.
    수가 5 1 9 2 7 4라면 표는 0 5 6 15 17 24 28이에요.
  • l번째부터 r번째까지의 합은 prefix[r] - prefix[l - 1]이에요.
    앞에서 r개의 합에서 앞의 l − 1개를 덜어 내면 그 사이만 남아요.
    표는 한 번만 만들고, 질문마다 뺄셈 한 번이면 돼요.
  • 표를 한 칸 더 길게(n + 1칸) 만들고 prefix[0] = 0으로 두면, l이 1일 때도 같은 식을 그대로 써요.
  • 두 포인터는 구간의 왼쪽 끝 left와 오른쪽 끝 right를 들고 있어요.
    right를 한 칸 늘려 수를 넣고, 합이 s 이상인 동안 길이를 적고 left를 한 칸 당겨 수를 빼요.
  • 두 자리 모두 뒤로 돌아가지 않아서 각각 많아야 n번 움직여요.
    모든 구간을 하나씩 해 보지 않아도 되는 까닭은, 수가 모두 양수라서 구간을 늘리면 합이 커지고 줄이면 작아지기 때문이에요.
  • 값이 10억쯤 되면 세 개만 더해도 32비트 정수(약 21억까지)를 넘어요.
    합을 담는 변수와 표는 64비트로 잡아요.

언어별로 쓰는 법

Pythonprefix = [0] * (n + 1)을 만들고 prefix[i + 1] = prefix[i] + a[i].
list(itertools.accumulate(a, initial=0))도 같은 표를 만들어요.
정수에 크기 제한이 없어요
JavaScriptnew Array(n + 1).fill(0).
수는 2^53(약 9천조)까지 정확해서 10억짜리 값 몇만 개의 합도 그대로 담아요
TypeScriptJavaScript와 같아요.
표의 타입은 number[]
Javalong[] prefix = new long[n + 1]; — 새 배열은 0으로 차 있어요.
합을 담는 변수도 long
C#long[] prefix = new long[n + 1]; — 새 배열은 0으로 차 있어요.
합을 담는 변수도 long
C++std::vector<long long> prefix(n + 1, 0);.
합을 담는 변수도 long long
Clong long prefix[10001];을 함수 밖에 두면 0으로 차 있어요.
찍을 때는 %lld
Craykonprefix = 새목록(n + 1, 0);.
수는 2^53까지 정확해요.
구간을 줄이는 반복은 동안 (window >= s) { }

자주 하는 실수

prefix[r] - prefix[l]로 뺐어요

a = [5, 1, 9, 2, 7, 4]
prefix = [0, 5, 6, 15, 17, 24, 28]
l, r = 2, 4
print(prefix[r] - prefix[l])

→ 11 — 2번째 수 1까지 빼 버렸어요. 맞는 답은 12예요

빼는 쪽은 prefix[l - 1]이에요.
l번째 수는 남아야 하니까 그 앞의 l − 1개만 덜어 내요.

구간을 줄일 때 while 대신 if를 썼어요

const a = [1, 1, 1, 10], s = 10;
let best = 0, left = 0, window = 0;
for (let right = 0; right < a.length; right++) {
  window += a[right];
  if (window >= s) {
    if (best === 0 || right - left + 1 < best) best = right - left + 1;
    window -= a[left];
    left++;
  }
}
console.log(best);

→ 4 — 맞는 답은 10 하나짜리 구간의 1이에요. 한 바퀴에 한 칸만 줄여서 left가 따라오지 못했어요

합이 s 이상인 동안 계속 줄여야 하니 while로 써요.

누적 합을 int에 담았어요Java · C# · C++ · C

int[] a = {1000000000, 1000000000, 1000000000};
int[] prefix = new int[4];
for (int i = 0; i < 3; i++) prefix[i + 1] = prefix[i] + a[i];
System.out.println(prefix[3]);

→ -1294967296 — 30억이 int(약 21억까지)에 들어가지 않아 넘쳤어요

표와 합 변수를 long(C·C++는 long long)으로 만들어요.
값 하나하나는 int에 들어가도 합은 넘칠 수 있어요.

언어마다 다른 점
누적 합은 값이 바뀌지 않는 목록에 합을 여러 번 물을 때 써요.
두 포인터로 합을 보는 이 방법은 수가 모두 양수일 때만 맞아요.
음수가 섞이면 구간을 늘려도 합이 줄 수 있어서, -1 5에서 합이 5 이상인 구간을 찾으면 5 하나를 놓치고 0을 내요.
번호를 0부터 세는지 1부터 세는지 먼저 정하고, 작은 예를 손으로 따라가 보세요.

연습 문제

  1. 두 입구의 입장 기록 합치기8P0260
  2. 구간 합 빨리 구하기8P0039
  3. 정렬된 수에서 합이 S인 두 수8P0069
  4. 버스가 가장 붐빈 구간8P0259
  5. 격자에서 직사각형 합 빨리 구하기8P0092
  6. 차이가 k 이하인 두 수8P0112
  7. 곱한 소수가 k개인 수 세기8P0113
  8. 목걸이에서 가장 짧게 끊어 내기8P0155