파이썬 자료구조 (1) 구간 합

구간 합

• 합 배열 S 정의
  • S[ i ] = A [ 0 ] + A [ 1 ] + A [ 2 ] + ... +  A [ i - 1 ] + A [ i ]
• 합 배열 S를 만드는 공식
  • S[ i ] = S[ i - 1 ] + A[ i ]
• 구간 합을 구하는 공식
  • S[ j ] - S[ i - 1 ]

 

예제 1) 구간 합 구하기 4 (백준 11659번)

 

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

 

파이썬 코드 

 

import sys
input = sys.stdin.readline
a, b = map(int, input().split())
num = list(map(int, input().split()))
sumList = [0]

for i in range(a):
    sumList.append(num[i] + sumList[i])

for i in range(b):
    k, q = map(int, input().split())
    print(sumList[q] - sumList[k-1])

 

예제 2) 구간 합 구하기 5 (백준 11660번)

 

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

 

파이썬 코드 

 

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):
    row = [0] + [int(x) for x in input().split()]
    a.append(row)
    
for i in range(1, n+1):
    for j in range(1, n+1):
        d[ i ][ j ] = d[ i-1 ][ j ] + d[ i ][ j-1 ] - d[ i-1 ][ j-1 ] + a[ i ][ j ]
        
for k 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)

 

 

합 배열과 구간 합 공식을 적재적소에 활용하면 코딩 테스트에서 시간 복잡도를 줄이는 데 많은 도움이 될 것입니다.