PostsSeriesLabsAlgo

기초 개념

누적합

구간의 합을 한 번 빼기로

하루하루 방문자 수가 10칸(0~9번)에 적혀 있습니다. 이런 질문 세 개를 풀 겁니다.

  • 2번 칸부터 6번 칸까지의 합은?
  • 1번 칸부터 8번 칸까지의 합은?
  • 0번 칸부터 9번 칸까지의 합은?

두 방법이 있습니다. 풀기 전에 골라 보세요. 어느 쪽이 덜 눌러도 될까요?

방문자 수

미리 깔아 둔 줄 — 앞에서 k칸을 더한 값 (작은 숫자가 k)

깔아 둔 줄의 예: 앞에서 3칸 합 = 3 + 1 + 4 = 8. 두 칸을 빼면 그 사이 칸의 합이 나옵니다.

손이 간 횟수 A 0 · B 0

손이 간 횟수는 A 가 0번, B 가 0번이었습니다.

방법 A · 칸을 하나씩 더하기23번
방법 B · 두 칸만 빼기6번
같은 세 질문. 질문이 늘수록 이 차이가 벌어집니다.

칸이 100만 개이고 질문이 1000개라면 이렇습니다.

방법 A · 질문마다 칸 전부 더하기1,000,000,000번
방법 B · 한 번 깔고 질문마다 두 칸1,002,000번
A 는 컴퓨터로 2분, B 는 1초 안입니다.

줄을 한 번 깔아 두고 구간의 합을 뺄셈 한 번으로 구하는 방법 = 누적합 (prefix sum)

  • 깔아 둔 줄 — 앞에서 k칸을 더한 값. 맨 앞은 앞에서 0칸이라 0
  • 구간의 합 — (끝 칸까지의 합) − (시작 칸 앞까지의 합)

질문이 여러 번일 때 이긴다

방법 B 도 공짜는 아닙니다. 줄을 깔 때 칸 수만큼 일합니다. 10칸에서 세어 보면 이렇습니다.

질문 1개 · 칸을 하나씩 더하기5번
질문 1개 · 깔고 빼기12번
질문 3개 · 칸을 하나씩 더하기23번
질문 3개 · 깔고 빼기16번
질문이 하나면 줄을 까는 품이 더 듭니다. 셋부터는 뒤집힙니다.
  • 질문이 여러 번 — 한 번 깐 줄을 계속 쓴다
  • 값이 안 바뀐다 — 한 칸이 바뀌면 그 뒤 줄이 전부 틀어진다

코드는 줄을 깔고 두 칸을 읽는다

방문자 수는 ①과 같은 10칸입니다. 2번 칸부터 6번 칸까지의 합을 구합니다. 다음을 눌러 아래 줄이 한 칸씩 깔리는 걸 보세요.

다음을 눌러 한 줄씩 넘겨 보세요

left = 2 right = 6

range_sum.py
  1. 1def range_sum(arr, left, right):
  2. 2 prefix = [0]
  3. 3 for i in range(len(arr)):
  4. 4 prefix.append(prefix[i] + arr[i])
  5. 5 ans = prefix[right + 1] - prefix[left]
  6. 6 return ans
0 / 24
  • prefix = [0] — 앞에서 0칸을 더한 값 0 에서 시작한다
  • prefix[i] + arr[i] — 앞에서 i칸 합에 i번 칸을 더하면 앞에서 i+1칸 합
  • prefix[right + 1] - prefix[left] — 끝 칸까지의 합에서 시작 칸 앞까지의 합을 뺀다

방문자 수가 [3, 1, 4] 이고 깔아 둔 줄이 [0, 3, 4, 8] 입니다. 1번 칸부터 2번 칸까지의 합은?

맨 앞 0 과 +1 에서 틀린다

  • prefix = [0] 를 빼먹으면 — 0번 칸부터 묻는 질문에서 틀린다. [3, 1, 4] 의 0번~1번 합은 4 인데 -4가 나온다. 오류도 안 난다. 파이썬은 -1 번 칸을 맨 뒤 칸으로 읽는다
  • right + 1 을 right 로 쓰면 — 끝 칸 하나가 빠진다. 깔아 둔 줄의 k번 칸은 앞에서 k칸의 합이라서 한 칸 밀려 있다
  • 값이 중간에 바뀌면 — 그 칸 뒤의 줄이 전부 틀어진다. 다시 깔아야 하니 질문 사이에 값이 바뀌는 문제에는 안 맞는다

문제에서 이 말이 보이면

구간의 합을 여러 번값은 안 바뀐다칸 수와 질문 수가 둘 다 크다

다음 장부터는 자료구조를 봅니다. 먼저 배열과 리스트입니다.