이 글은 https://movingbean.tistory.com/17 의 블로그에서 작성된 내용을 바탕으로 정리 + @한 글입니다. 누적 합에 대한 내용이 너무 잘 정리되어 있습니다!!!!!! 꼭 보시길 바랍니다.
- 1차원 공간 vs 2차원 공간
- 점 업데이트 vs 구간 업데이트
- 점 쿼리 vs 구간 쿼리 (특정 위치에 대한 개수만을 묻는가? vs 어떤 구간의 총합을 묻는가?)
- 오프라인 쿼리 vs 온라인 쿼리 (질문을 업데이트가 모두 끝나고 하는가? vs 업데이트 도중에 질문을 하는가?
1. 1차원 공간, 점 업데이트, 오프라인 쿼리
점 업데이트라는 것은 초기 값만 세팅하는 경우도 점 오프라인으로 볼 수 있다고 한다. 가장 기본적으로 누적 합(PrefixSum)을 구하는 것을 떠올릴 수 있다.
시간 복잡도는 누적 합을 구하는 데 O(N), M개의 쿼리를 처리하는 데 각각 O(1)이므로, O(N + M)
[백준] 구간 합 구하기 : https://www.acmicpc.net/problem/11659
import sys
si = sys.stdin.readline
n,m=map(int,si().split())
arr=list(map(int,si().split()))
prefix_sum=[0] * (len(arr)+1)
for i in range(len(arr)) :
prefix_sum[i+1] = prefix_sum[i] + arr[i]
for _ in range(m):
start,end=map(int,si().split())
print(prefix_sum[end]-prefix_sum[start-1])
2. 1차원 공간, 구간 업데이트, 오프라인 쿼리
오프라인 쿼리의 구간 업데이트의 경우, imos 기법을 사용하면 구간 업데이트가 O(1)에 가능하다. 간단한 예시와 함께 살펴본다. PC방에 머무른 손님들의 정보를 그림으로 표현했다고 가정해본다.
각 구간[s,e]에 대해 for문을 돌리는 것이 아니라 입장하는 부분 +1, 퇴장하는 부분 -1을 설정한다. 그리고 왼쪽부터 전체 누적합을 구해준 뒤, 구간 [i, j]의 합은 sum[j] - sum[j - 1]로 쉽게 구할 수 있다.
1차원 배열에서 점 업데이트를 구하는 방법과 비슷하다. 둘의 차이를 비교해보자.
누적합과의 비교
누적합
- 입력을 다 받고, 전처리 한번 거치고 나면, [s, e]의 합을 구하는 것과 같은 쿼리를 빠르게 처리할 수 있다.
- 쿼리 처리 도중 값 갱신이 일어나지 않는 경우에 사용한다.
imos법
- 여러 개의 쿼리가 구간 [s, e] 내의 값을 갱신시키는 경우, 매 쿼리마다 일일이 갱신하지 않고, 시작과 끝만 기록해두었다가 마지막에 한 번의 처리로 값을 시뮬레이팅하는 방법
시간 복잡도는 누적 합을 두 번 구하는데 각각 O(maxTime), M개의 쿼리를 처리하는 데 각 O(1)이므로 O(maxTime + M)
[백준] 시간 구간 다중 업데이트 다중 합 : https://www.acmicpc.net/problem/25827
import sys
si = sys.stdin.readline
n = int(si())
sz = 24*60*60
arr = [0] * (sz+1)
imos = [0] * (sz+1)
flag = False
def init() :
global flag, sz
if flag : return
flag = True
for i in range(1,sz+1) :
arr[i] += arr[i-1]
imos[i] = imos[i-1] + arr[i]
for _ in range(n) :
types, start, end = si().split()
start_hour, start_min, start_sec = list(map(int,start.split(":")))
end_hour, end_min, end_sec = list(map(int,end.split(":")))
s_time = start_hour*3600 + start_min*60 + start_sec
e_time = end_hour*3600 + end_min*60 + end_sec
s_time, e_time = s_time+1, e_time+1 # 1부터 시작하도록 1칸 이동
if types == '1' :
arr[s_time] += 1
arr[e_time] -= 1
else :
init()
print(imos[e_time-1] - imos[s_time-1])
3. 2차원 공간, 점 업데이트, 오프라인 쿼리
1번 문제에서 2차원 공간으로 확장되었다.
초기 누적합을 구해두고, 각 입력에 맞는 구간의 합을 출력하면 된다. 시간 복잡도는 초기 N^2개의 값 세팅에 따라 각각 O(1), M개의 쿼리를 처리하는 데 각각 O(1)이므로 O(N^2 + M)
[백준] 구간 합 구하기 5 : https://www.acmicpc.net/problem/11660
import sys
si = sys.stdin.readline
n,m=map(int,si().split())
prefix_sum=[[0]*(n+1) for _ in range(n+1)]
board=[list(map(int,si().split())) for _ in range(n)]
for i in range(1,n+1) :
for j in range(1,n+1) :
prefix_sum[i][j] = board[i-1][j-1] + prefix_sum[i][j-1] + prefix_sum[i-1][j] - prefix_sum[i-1][j-1]
for _ in range(m) :
r1,c1,r2,c2=map(int,si().split())
r1-=1;c1-=1;r2-=1;c2-=1
ans = prefix_sum[r2+1][c2+1] - prefix_sum[r2+1][c1] - prefix_sum[r1][c2+1] + prefix_sum[r1][c1]
print(ans)
4. 2차원 공간, 구간 업데이트, 오프라인 쿼리, 점 쿼리
2번 문제에서 2차원 공간으로 확장된 경우이다.
이 글에서 유일한 점 쿼리 문제이고, 특정 건물(점)의 파괴 여부를 묻는 상황이다. 5번 문제와 똑같이 누적 합을 구해주면 되고, 점을 묻는 문제이므로 해당 건물(점)에 대한 연산만 수행해주면 된다.
시간복잡도는 초기 N*M개의 값 세팅에 각각 O(1), Q개의 쿼리를 처리하는 데 각각 O(1), 누적 합을 구하는데 O(NM), 파괴되지 않은 건물의 개수를 구하는데 O(NM)이므로 O(NM + len(skill))
[프로그래머스] 파괴되지 않은 건물 : https://school.programmers.co.kr/learn/courses/30/lessons/92344
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
def solution(board, skill):
r = len(board)
c = len(board[0])
prefix_sum = [[0] * (c+1) for _ in range(r+1)]
for i in range(len(skill)) :
ty, r1,c1,r2,c2,degree = skill[i]
if ty == 1 :
prefix_sum[r1][c1] += degree
prefix_sum[r2+1][c2+1] += degree
prefix_sum[r1][c2+1] -= degree
prefix_sum[r2+1][c1] -= degree
else :
prefix_sum[r1][c1] -= degree
prefix_sum[r2+1][c2+1] -= degree
prefix_sum[r1][c2+1] += degree
prefix_sum[r2+1][c1] += degree
for i in range(len(prefix_sum)) :
for j in range(1,len(prefix_sum[i])) :
prefix_sum[i][j] = prefix_sum[i][j-1] + prefix_sum[i][j]
for j in range(len(prefix_sum[0])) :
for i in range(1,len(prefix_sum)) :
prefix_sum[i][j] = prefix_sum[i-1][j] + prefix_sum[i][j]
answer = 0
for i in range(len(board)) :
for j in range(len(board[i])) :
board[i][j] -= prefix_sum[i][j]
if board[i][j] > 0 : answer += 1
return answer
다음 글에서는 온라인 쿼리 기반의 케이스들을 다뤄보겠다. 온라인 쿼리를 다루기 전에 세그먼트 트리에 대한 사전 지식을 필요로 하니까 아래 블로그에서 먼저 공부하시길 바란다.
- https://blog.naver.com/kks227/220791986409 (세그먼트 트리)
- https://blog.naver.com/kks227/220824350353 (세그먼트 트리 with lazy propagation)
출처
[Algorithm/C++] 1,2차원에서의 구간 합 구하기 (+백준 연습문제, kakao 기출문제)
이번 글에서는, 아래의 네 가지 조건으로 만들어지는 다양한 상황에서 알맞은 방식으로 구간 합을 구하는 테크닉을 소개하려고 합니다. 1차원 공간 vs 2차원 공간 점 업데이트 vs 구간 업데이트
movingbean.tistory.com
누적합의 확장, imos법
imos법에 대해 알아보자.
driip.me