구간 합
개요
어떤 리스트가 주어진다.
[15, 10, 11, 12, 6, 4]
여기서 특정 구간의 합을 구하려면 어떻게 하는 것이 좋을까?
예를 들어 2번째 요소인 10부터 5번째 요소인 6까지의 합을 구해보자.
start = 1
end = 4
numbers = [15, 10, 11, 12, 6, 4]
sum_val = sum(number[start:end + 1])
전체 시간복잡도는 O(N)이 된다.
구간 합
구간 합이란 합 배열을 미리 만들어둔 뒤 이를 이용해서 매번 합을 구하지 않고 시간복잡도 o(1)로 구간 합을 구할 수 있는 방법이다.
위의 자료를 가지고 구간합 리스트를 만들어보자면 다음과 같다.
[15, 25, 36, 48, 54, 58]
Q) 만약 2번째 자료부터 5번째 자료까지의 합을 구하려면?
A) s[4]-s[1]을 구하면 된다.
예제
백준 11659
문제
수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.
출력
총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.
제한
1 ≤ N ≤ 100,000
1 ≤ M ≤ 100,000
1 ≤ i ≤ j ≤ N
처음 고려해본 방법으로 문제를 푼다면 구간에 대해 순차적으로 더하는 시간복잡도 O(N), M번의 구간합을 계산해야하기 때문에 시간복잡도는 O(N*M)으로 최대 100,000개의 데이터에 대해 최대 질의의 수 100,000번의 연산을 수행해야하기 때문에 제한시간내에 풀 수 없게된다.
import sys
input = sys.stdin.readline
numbers_length, query_length = map(int, input().split())
numbers = list(map(int, input().split()))
temp = 0
prefix_sum = [0]
for i in numbers:
temp = temp + i
prefix_sum.append(temp)
for i in range(query_length):
s, e = map(int, input().split())
print(prefix_sum[e] - prefix_sum[s-1])
백준 11660
문제
N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다.
예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자.
1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7
여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이고, (4, 4)부터 (4, 4)까지 합을 구하면 7이다.
표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오.
입력
첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 개의 정수 x1, y1, x2, y2 가 주어지며, (x1, y1)부터 (x2, y2)의 합을 구해 출력해야 한다. 표에 채워져 있는 수는 1,000보다 작거나 같은 자연수이다. (x1 ≤ x2, y1 ≤ y2)
출력
총 M줄에 걸쳐 (x1, y1)부터 (x2, y2)까지 합을 구해 출력한다.
예제 입력 1
4 3
1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7
2 2 3 4
3 4 3 4
1 1 4 4
예제 출력 1
27
6
64
예제 입력 2
2 4
1 2
3 4
1 1 1 1
1 2 1 2
2 1 2 1
2 2 2 2
예제 출력 2
1
2
3
4
이전의 문제와 같이 쿼리의 개수가 100,000개다. 구간 합을 이용하지 않으면 시간초과가 생긴다.
일단 첫번째 행과 열의 합 리스트를 갱신한다. 합배열은 합배열[1][2] = 합배열[1][1] + 원본배열[1][2]와 같이 갱신하면 된다.
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
A = [[0] * (n+1)]
D = [[0] * (n+1) for _ in range(n+1)]
for i in range(n):
A_row = [0] + [int(x) for x in input().split()]
A.append(A_row)
for i in range(1, n+1):
for j in range(1, n+1):
D[i][j] = D[i][j-1] + D[i-1][j] - D[i-1][j-1] + A[i][j]
for _ in range(m):
x1, y1, x2, y2 = map(int, input().split())
result = D[x2][y2] - D[x1-1][y2] - D[x2][y1-1] + D[x1-1][y1-1]
print(result)
백준 10986
문제
수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오.
즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다.
입력
첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 106, 2 ≤ M ≤ 103)
둘째 줄에 N개의 수 A1, A2, ..., AN이 주어진다. (0 ≤ Ai ≤ 109)
출력
첫째 줄에 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 출력한다.
예제 입력 1
5 3
1 2 3 1 2
예제 출력 1
7
예를 들어 A/B를 Q라고 하고 그 나머지를 R이라고 하자.
보통은 몫을 구하지만 나머지를 구할 때 사용하는 연산자를 모듈로 연산자라고 한다.
즉, A mod B = R로 표현할 수 있다.
만약 A = B(mod C)와 같다면 이를 A와 B는 모듈 C에 대한 합동 관계라고 한다.
만약 모든 정수에 대해 mod 5를 계산한다고 해보자.
5로 나눈 나머지는 0, 1, 2, 3, 4가 있을 수 있으므로 5개의 양동이를 준비한다.
그런 뒤 mod 5의 결과가 같은 정수들을 해당하는 양동이에 넣는다.
어떤 두 값이 같은 양동이에 들어있다는 것을 두 값이 같은 동치류에 있다고 표현한다.
A ≡ B(mod C)
이 모듈로 연산은 여러 규칙을 가진다.
예를 들어
(A + B) % C = ((A % C) + (B % C)) % C가 성립한다.
위의 문제의 경우 주어진 배열을 이용해 합 배열을 생성한다.
그런 다음 모든 값을 나머지 연산한 뒤 값을 업데이트한다.
나누어 떨어지는 구간의 개수를 구하라고 했으니 나머지 연산을 한 결과가 0인 요소를 카운트한다.
이는 원본 리스트의 0부터 i까지의 구간 합이 M으로 떨어진다는 의미이기 때문이다.
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
A = list(map(int, input().split()))
S = [0] * n
C = [0] * m
S[0] = A[0]
answer = 0
for i in range(1, n):
S[i] = S[i-1] + A[i]
for i in range(n):
remainder = S[i] % m
if remainder == 0:
answer += 1
C[remainder] += 1
for i in range(m):
if C[i] > 1:
answer += (C[i] * (C[i] - 1) // 2)
print(answer)