구간 합

구간 합

합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘

 

구간 합의 핵심 이론

구간 합 알고리즘을 활용하려면 먼저 합 배열을 구해야 함

 

합 배열 S 정의

S[i] = A[0] + A[1] + A[2] + … + A[i-1] + A[i]   # S[i]는 A[0]부터 A[i]까지의 합

인덱스	0	1	2	3	4	5
배열 A	15	13	10	7	3	12
합 배열 S	15	28	38	45	48	60

 

합 배열 S를 만드는 공식

S[i] = S[i-1] + A[i]

 

i에서 j까지 구간 합을 구하는 공식

S[j] - S[i-1]

ex) A[2]부터 A[5]까지의 합 = A[0]부터 A[5]까지의 합 - A[0]부터 A[1]까지의 합 = S[5] - S[1]

 

[문제 003] 구간 합 구하기 1

import sys
input = sys.stdin.readline

N, M = map(int, input().split()) # 데이터의 개수, 질의 개수
a = list(map(int, input().split())) # 구간 합을 구할 배열

# 합 배열 구하기
s = [0] * (N+1) # 합 배열
for n in range(1, N+1):       
    s[n] = s[n-1] + a[n-1]

# i에서 j까지의 구간 합        
for _ in range(M):
    i, j = map(int, input().split())
    print(s[j] - s[i-1])

 

[문제 004] 구간 합 구하기 2 →  풀이

import sys
input = sys.stdin.readline

n, m = map(int, input().split()) # 표의 크기, 합을 구해야 하는 횟수

A = [] # NxN 리스트
for _ in range(n):
    A.append(list(map(int, input().split())))
    
# 합 배열 D 구하기
D = [[0] * (n+1) for _ in range(n+1)] # DP 테이블
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] # 구간 합

# x1,y1에서 x2,y2까지의 합        
for _ in range(m):
    x1, y1, x2, y2 = map(int, input().split())
    print(D[x2][y2] - D[x1-1][y2] - D[x2][y1-1] + D[x1-1][y1-1])

 

[문제 005] 나머지 합 구하기 →  풀이

n, m = map(int, input().split()) # n개의 수, M으로 나누기
A = list(map(int, input().split())) # n개의 수로 이루어진 원본 배열

S = [] # 합 배열
mod_count = [0] * m

temp = 0
for i in A:
    temp += i
    S.append(temp) # 누적 합
    mod_count[temp % m] += 1 # 누적 합 % m
    
# m으로 나누어 떨어지는 (i, j) 순서쌍의 개수
answer = mod_count[0] # 나누어 떨어지는 경우 = (i, i)
for i in mod_count:
    answer += i * (i-1) // 2 # i개 중에 2개를 뽑는 경우의 수(iC2)

print(answer)

 

참고: Do it 알고리즘 코딩테스트: 파이썬 편