누적합 알고리즘(1차원, 2차원 누적합)

누적합 알고리즘은 1~N까지 합을 효율적으로 구할 수 있는 알고리즘이다.

 

1

1 + 2

1 + 2 + 3

1 + 2 + 3 + 4

 

라고하면

 

sum[1] = 1

sum[2] = 3

sum[3] = 6

sum[4] = 10

 

이고 여기서 2~4까지의 합을 구하면 sum[4] - sum[1] 과 같다. 즉 answer = sum[end] - sum[start - 1] 이다.

 

그리고 중요한건 모든 sum 배열을 구성하는 것이다. 이 때 O(N^2)의 시간을 사용하는 것은 너무 비효율적이다. 효율적으로 사용하기 위해 sum[2] = sum[1] + arr[2]

sum[3] = sum[2] + arr[3]

.

.

.

 

식을 사용하면 O(N)으로 prefix배열을 구성할 수 있다. 1차원 배열 누적합은 쉽게 구성이 가능하다.

 

이것을 응용하면 2차원 배열에서도 누적합을 구성할 수 있다. 2차원 누적합의 개념은 다음과 같다.

검은색 : 1,1 ~ 3, 4까지 모두 더한 것

파란색 :  1,2 ~ 3, 3 까지 더한 것

빨간색 : 1,1 ~ 1, 2 까지 모두 더한 것

 

즉 한 좌표가 왼쪽 위 다른 한 좌표가 오른쪽 아래가 되어 누적합이 이루어진다. 

 

그리고 이것을 어떻게 구할 수 있을까

 

prefixsum[2][4]를 구하려면?

 

prefixsum[2][4]를 구한다고 가정했을 때, 사진의 초록색을 모두 더한 부분인 prefixsum[1][4], 빨간색을 모두 더한 부분인 prefixsum[2][3]을 더하고 2,4 지점의 값을 더해주면 된다. 그런데 초록색 부분과 빨간색 부분은 겹치는 부분이 있다. 저 겹치는 부분을 빼줘야한다. 그래서 이것을 점화식으로 나타내면 다음과 같다.

 

 

코드로 나타내면

 

	for(int i = 1; i <= N; i++){
		for(int j = 1; j <= N; j++){
        	prefixsum[i][j] = prefixsum[i-1][j] + prefixsum[i][j-1] 
           					 - prefixsum[i-1][j-1] + arr[i - 1][j - 1];
		}
	}

 

누적합 알고리즘은 은근 출제 빈도가 높으므로 알고가는 것이 좋다.