[Algorithm] 누적합

연관 문제

• tony9402님 누적합 문제집
• BOJ 2167 2차원 배열의 합
• BOJ 20440 니가 싫어 싫어 너무 싫어 싫어 오지 마 내게 찝쩍대지마🎵 - 1
• hackerrank Array Manipulation

00. 개요

A부터 B까지의 합을 미리 구해놓고 쓰자!

• 예를 들어 1월부터 12월까지 데자와 판매량이 있을 때, 특정 구간의 평균 판매량 데이터를 구해야 하는 경우
  • 매번 구간의 합을 구한다고 생각하면 횟수가 늘어날수록 비효율적이다!

01. 배열의 누적합

1 ) 1차원 배열

배열을 하나 더 두고 누적 합을 계산해나간다.

int arr[5] = {1,2,3,4,5};
int accumArr[6] = {0, 1, 3, 6, 10, 15};
/**
accumArr[1] = arr[0] ;
for(int idx = 1 ; idx < 5; ++idx){
    accumArr[idx+1] = accumArr[idx] + arr[idx];
}
*/
// arr index 3번부터 4번까지의 합 계산하기 (0<=idx<5)
int result = accumArr[5] - accumArr[3]
// accumArr[dest]-accumArr[start-1];
// start index가 0으로 주어지는 경우, 
// 오류 방지를 위해 accumArr을 N+1개로 선언하여 accumArr[0]를 만들어줌

2 ) 2차원 배열

(x, y)부터 (i, j)까지의 누적합을 구한다.
${\rightarrow}$ (x, y)와 (i, j)가 이루는 직사각형의 면적
${\Rightarrow}$ 사각형을 그리고, 겹치는 면적을 생각해서 계산

// (0, 0)과 (n, m)이 이루는 직사각형 내의 값들의 합 구하기

for (int n = 1; n <= N; ++n) {
	for (int m = 1; m <= M; ++m) {
		accumArr[n][m] = accumArr[n][m - 1] + accumArr[n - 1][m] + arr[n][m] - accumArr[n - 1][m - 1];
	}
}
    
// (sn, sm)와 (en, em)이 이루는 직사각형 내의 값들의 합 구하기 
result = accumArr[endN][endM] - accumArr[endN][startM - 1] - accumArr[startN - 1][endM] + accumArr[startN - 1][startM - 1];

02. 응용 : Dictionary (BOJ 20440)

참고

• C++에서 unordered_map 대신 map을 사용하면 TLE가 난다.
  • map과 unordered_map의 구현 차이
  • map은 Red-Black Tree로 구현되어 있고, unordered_map은 hash로 구현되어 있다.
    ${\rightarrow}$ 탐색 시간이 차이남
    • 참고 : gracefulprograming님 map vs hash_map(unordered_map)

from collections import defaultdict
import sys

input = sys.stdin.readline

N = int(input())
enter_exit_dict = defaultdict(int)

for n in range(N):
    
    s, e = map(int,input().split(' '))
    enter_exit_dict[s] += 1 
    enter_exit_dict[e] -= 1

sorted_key_list = sorted(enter_exit_dict.keys())

cnt = 0 
result = 0 # 최대 모기 수 
result_t_s = 0 
result_t_e = 0 
can_check = False 

for k in sorted_key_list:

    cnt += enter_exit_dict[k]
    
    # 모기가 제일 많은 시간대 시작!
    if(cnt > result):
        result = cnt
        result_t_s = k
        can_check = True 

    elif( cnt < result and can_check == True):
        result_t_e = k
        can_check = False

print(result)
print(f'{result_t_s} {result_t_e}')