[ 구간 합 ] 알고리즘

 

 

구간 합 알고리즘

    

      1)  구간 합 알고리즘 : 합 배열을 통해 기존 리스트의 일정 범위의 합을 구하는 알고리즘

            * 시간 복잡도 : O(1)

 

 

       2) 구현

 

            (1) 합 배열 만들기

 

                    합 배열 : 기존 리스트 0 ~ i 번까지의 합 

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

인덱스	0	1	2	3	4
리스트 A	1	2	3	4	5
합 배열 S	1	3	6	10	15

       

            (2) 구간 합 구하기

 

                     구간 합 : 기존 리스트 a ~ b 번까지의 합

                      prefixSum = S[b] - S[a-1]

인덱스	0	1	2	3	4
리스트 A	1	2	3	4	5
합 배열 S	1	3	6	10	15

                       

                    리스트 A의 인덱스 1번 ~ 3번까지의 구간 합은

                    A[1] + A[2] + A[3] = (A[0] + A[1] + A[2] + A[3]) - (A[0]) = S[3] - S[0]

                    -> S[3] - S[0] 으로 구하면 된다

 

 

      3)  문제 풀이

 

# 1  구간 합 구하기 1 - 백준 11659번

 

일차원 구간 합

 

https://www.acmicpc.net/problem/11659

11659번: 구간 합 구하기 4

 

 

N,M = map(int,input().split())
num = list(map(int, input().split()))

# 합 배열 생성
sumList = []
sum = 0
for a in range(N):
    sum+=num[a]
    sumList.append(sum)
    
# 구간 합
p_sumList = []

for k in range(M):
    # i,j : 범위
    i, j = map(int, input().split())
    if i == 1:
        p_sumList.append(sumList[j-1])
    else:
        p_sumList.append(sumList[j-1] - sumList[i-2])

for b in range(len(p_sumList)):
	print(p_sumList[b])

 

 

# 2  구간 합 구하기 2 - 백준 11660번

 

이차원 구간 합

 

https://www.acmicpc.net/problem/11660

11660번: 구간 합 구하기 5

 

 

 

import sys 
input = sys.stdin.readline 

n, m = map(int,input().split())

# A : 데이터 리스트 -> 리스트의 인덱스는 0부터 시작하기 때문에 헷갈리지 않기 위해 (n+1)칸 만듦
A = [[0] * (n+1)]

for i in range(n):
    A_row = [0]+[int(x) for x in input().split()]
    A.append(A_row)

# D : 합 배열 -> 리스트의 인덱스는 0부터 시작하기 때문에 헷갈리지 않기 위해 (n+1)칸씩 만듦
D = [[0] * (n+1) for _ in range(n+1)]

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)

 

 

 

+) 2023.03.04  알고리즘 스터디에서 

# 3 나머지 합 - 백준 10986번 

 

https://www.acmicpc.net/problem/10986

10986번: 나머지 합

 

 

 

n,m = map(int,input().split())
num = list(map(int, input().split()))

ps = [0]
left = []

sum = 0

zero = 0
sameNum = [0]*(m+1)
sN = 0

# 합 배열 생성
for i in num:
    sum += i
    ps.append(sum)

# 나머지 배열 생성
for j in ps:
    leftover = j % m
    left.append(leftover)
    
    # 나머지 배열에서 '요소의 값'이 0인 것의 개수
    if leftover == 0:
        zero+=1
        
    # 나머지 배열에서 같은 값의 개수 저장   
    if leftover > 0:
        sameNum[leftover] += 1

# 같은 값 2개 선택하는 경우 - 나머지 배열에서 같은 값의 개수가 1보다 크면 조합 사용
for k in sameNum:
    if k > 1:
        sN += k*(k-1) / 2

# 0의 개수
sN += zero-1

# 0 2개를 선택하는 경우 - 조합 사용
sN += (zero-1)*(zero-2) / 2

print(int(sN))