[코드트리 조별과제] prefix sum

우하하.. 이때를 위해 만들어놨달까요😝

 

ㅎㅎ해야 하는데, 많이 하지는 못했네요

이번주에는 prefix sum을 봤습니다. 그냥.. 알고있는 누적합이에요!

 

개념은 간단해서

뭔가 포인트는 어떤 문제에서 -> 누적합을 쓴다는 생각으로 이어지는게 중요한 것 같아요

 

누적합(prefix sum)

누적합은 특정 배열의 누적합을 구해놓고, 그것을 사용해서 구간을 탐색하는 횟수를 줄인 테크닉입니다.

 

구간 내 숫자의 합을 빠르게 구하는 데 사용하기 좋습니다.

특히, 특정 배열이 처음 정해져서 변동되지 않고, 쿼리가 많이 주어져서 그 배열 탐색을 자주 해야 하는 경우에 사용하면 좋은 것 같아요

 

1차원 배열에서 누적합

arr라는 배열의 누적합을 구한 s라는 배열을 만들어 봅시다.

s[1]는 arr의 원소 1개의 누적합이, s[2]에는 arr의 원소 2개의 누적합이, .. s[i]에는 arr 원소 i개의 누적합이 들어있어야 합니다. 

구간 [a,b]에서의 누적합을 구하기 위해서는 s[b]-s[a-1]을 하면 됩니다!

a번째부터 b번째 원소들의 합을 구해야 하므로... 1번째부터 b번째 원소의 합(=s[b])에서 1번째부터 a-1번째 원소의 합(=s[a-1])를 빼주면 됩니다.

 

빼기를 쉽게(조건 없이) 진행하기 위해, 보통 누적합의 0번째 인덱스 값을 0으로 지정해둡니다  

 

대표적 예시 문제로, 연속된 k개 원소의 합 중 최댓값을 구하는 문제입니다!

n,k=map(int,input().split())
arr=list(map(int,input().split()))
s=[0]
for i in range(n):
    s.append(s[-1]+arr[i])
ans=0
for i in range(k,n+1):
    ans=max(ans,s[i]-s[i-k])
print(ans)

저는 이런 식으로 파이썬 코드를 작성했습니다!

만약, 인덱스가 헷갈린다면 arr의 0번째 인덱스에도 0을 넣음으로써 인덱스를 맞추는 방법도 가능합니다.

 

2차원 배열에서의 누적합

(a,b)~(c,d) 안에서의 누적합을 찾아야 하는 경우 사용할 수 있습니다.

(a,b)가 (1,1)~(a,b)까지의 누적합이면.... 

(a,b)~(c,d) 안에서의 누적합은 [(1,1)~(c,d)] - [(1,1)~(a-1,d)] - [(1,1)~(c,b-1)] + [(1,1)~(a-1,b-1)] 라는 공식으로 구할 수 있습니다. 즉 S[c][d] - S[a-1][d] - S[c][b-1] + S[a-1][b-1]를 하면 되지요

 

그림으로 이해하자면, 2번 빠졌기 때문에 마지막에 S[a-1][b-1]을 더함으로써 그 영향을 없애주는 겁니다.

 

2차원 배열을 사용하는 대표적인 문제로, k*k의 정사각형의 합 중 최댓값을 찾는 문제입니다!

import sys
input=sys.stdin.readline
n,k=map(int,input().split())
arr=[list(map(int,input().split())) for _ in range(n)]
s=[ [0]*(n+1) for _ in range(n+1)]

for i in range(n):
    for j in range(n):
        s[i+1][j+1]=arr[i][j]+s[i][j+1]+s[i+1][j]-s[i][j]

ans=0
for i in range(k,n+1):
    for j in range(k,n+1):
        ans=max(ans,s[i][j]-s[i][j-k]-s[i-k][j]+s[i-k][j-k])
print(ans)

저는 이렇게 코드를 짰습니다!

 

포인트는, 누적합을 구하는 방식이었는데요! 내가 어떻게 구해가야 하는지를 잘 생각하고 식을 작성해야해요...!

오히려 얘는 이전 것들에 더해야 하는 방식이므로 식이 약간 다른 것을 확인할 수 있습니다.

 

 

예제 문제를 풀면서 마무리해볼게요

 

원래 최대 직사각형의 합 문제를 풀어볼까 했으나.. 아직 풀지 못해... 대표적인 예시와 공부한 내용만 올립니다😂