[Algorithm] 누적 합 (Prefix Sum)

누적 합 문제는 1차, 2차원 상태의 배열과 연관된 문제가 주를 이룬다.

 

누적 합, 말 그대로 현재까지의 모든 값을 누적 합산한 결과를 새로운 배열에 저장하고, 내가 원하는 범위의 누적 합을 빠르게 계산해낼 수 있다.

누적 합을 계산해 갈 때 내 이전의 누적 값을 불러오는 점화식이 활용되므로, 누적 합 배열의 첫 인덱스는 0으로 초기화 해주는 것이 중요하다.

 

※ 단, 연속된 구간의 합을 구하는 문제는 투포인터를 활용해 더 간단하게 해결할 수 있으니 주의하자.

 

1차원 상태의 배열에 대한 누적 합을 구하는 방법은 간단하다.

누적 합 자체의 정의에 맞는 점화식을 세워, 내가 원하는 구간의 합을 구할 수 있다

prefixSum[0] = 0;
for(int i = 1; 1 <= N; i++) {
	prefixSum[i] = value[i] + prefixSum[i-1];
}

 

2차원 상태의 배열에 대한 누적 합을 구하는 방법은 다소 난해하다.

1차원 상태의 배열에 대한 누적 합을 활용하여, 2차원 상태의 모든 범위를 더해야 하기 때문이다.

 

2차원 상태의 배열의 누적 합은, 내가 원하는 인덱스 (x, y)가 존재할 때 (0, 0), (0, x), (y, 0), (x, y)를 꼭짓점으로 하는 정사각형 내의 모든 인덱스의 합이다.

이를 풀어서 말하면 (0, 0)을 기준으로 행으로 x만큼, 열로 y만큼의 모든 행열을 더한 값을 누적 합 배열(x, y)에 저장한다.

 

하지만, 누적 합 배열의 갱신하기 위해선 내 이전의 누적 값을 활용해야 한다. 늘어나는 행열의 새로운 값을 반복문을 통해 직접 찾아간다면 시간복잡도는 다시 O(N^2)이 될 뿐이다.

그래서 우리는 (x, y)의 값 그리고 (x - 1, y)의 누적 합과 (x, y - 1)의 누적 합 그리고 (x - 1, y - 1)의 누적 합을 활용해 (x, y)에 대한 누적 값을 갱신 할 것이다.

이 때, (x - 1, y)와 (x, y - 1)의 누적 합에는 (x - 1, y - 1)의 누적 합이 포함된다. 그러므로 모든 값을 합산할 때, (x - 1, y - 1)의 누적 합은 곱절이되므로 한번 빼주어야 한다. 그에 대한 점화식은 다음과 같다.

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

 

 

내가 원하는 구간의 누적 합을 구하고 싶은 경우엔, 그림판에서 정사각형을 그리는 것이라고 생각하면 조금 더 이해하기 편할 수 있다.

정사각형을 그리는 시작 인덱스를 (s1, s2) 그리고 마지막 인덱스를 (e1, e2)라고 한다면,

우리는 (e1, e2)의 누적 합에서, (s1 - 1, s2 - 1)의 누적 합을 제거해야하며 (0, 0) ~ (s1 - 1, e2)  그리고 (0, 0) ~ (e1, s2 - 1)의 누적 합을 제거해야 한다.

 

우리는 (s1, s2)부터 (e1, e2)에 포함된 모든 배열에 대한 합을 구해야하므로, 그 전의 누적 합을 구할 수 있는 s1 - 1, s2 - 1행열의 누적 합을 구하는 것이다.

 

위 내용은 다양한 변수가 활용되었기 때문에 시작점을 (i, j) 그리고 끝점을 (i+k, j+k)라고 한다면,

우리는 (i+k, j+k)의 누적합에서, (i - 1, j - 1)의 누적 합을 제거해야 하며 (i - 1, j+k) 그리고 (i+k, j - 1)의 누적 합을 제거해야 한다.

이 때, 뺄셈이 곱절이 되므로 (i - 1, j - 1)의 누적 합을 한번 더해주어야 한다. 이를 점화식으로 나타내면 다음과 같다.

for (int i = 1; i <= N; i++)
	for (int j = 1; j <= N; j++) {
    		int result = prefixSum[i + k][j + k]
            		- prefixSum[i - 1][j + k] 
                	- prefixSum[i + k][j - 1] 
                	+ prefixSum[i - 1][j - 1];
		}
	}