[알고리즘] 누적합(prefix sum)

안수진·2024년 2월 20일

Algorithm

목록 보기

21/22

누적합에 대해 공부하기 전
구간합 개념을 잘 모르겠다면 보고오자!
[Java - Do it!] 구간 합

🔎 누적 합(prefix sum)

// N개의 수를 입력받아 배열에 저장하면서 prefixSum도 함께 만든다.
int[] arr = new int[N+1];
for (int i = 1; i <= N; i++) {
    int num = nextInt();
    arr[i] = arr[i-1] + num;
}

// a와 b를 입력받아 a번째부터 b번째까지의 합을 구해 answer[]에 담는다.
int[] answer = new int[M+1];
for (int i = 0; i < M; i++) {
    int a = nextInt();
    int b = nextInt();
    answer[i] = arr[b] - arr[a-1];
}

🔎 1차원 누적합

prefixSum[x]는 1번째부터 x번째까지의 합을 나타낸다.

🔎 2차원 누적 합

prefixSum[x][y]는 (1,1)부터 (x,y)까지의 합이라고 해보자.

(인덱스는 1번부터 사용)

빨간 부분 (3, 3)부터 (5, 5)의 합을 어떻게 구할 수 있을까?

prefixSum[5][5]는 (1,1)부터 (5,5)까지의 합을 나타내므로
해당 부분에서 저 녹색 부분prefixSum[2,5]을 빼주고
노란 부분prefixSum[5][2]을 빼주고
중복되어 삭제되는 prefixSum[2][2]를 한번 더 더해주면 된다.

즉, (3,3)부터 (5,5)까지의 2차원 구간합은

prefixSum[5][5] - prefixSum[5][3-1] - prefixSum[3-1][5] + prefixSum[3-1][3-1] = 36

🧐 (x1, y1)부터 (x2, y2)까지 2차원 구간합

(x1 ≦ x2, y1 ≦ y2)

prefixSum[x2][y2] - prefixSum[x2][y1-1] - prefixSum[x1-1][y2] + prefixSum[x1-1][y1-1]

🔎 (1,1)부터 (x,y)까지의 합은 어떻게 구할까?

빨간 글자 부분(4,4)에 해당하는 prefixSum[4][4]는

prefixSum[4-1][4] + prefixSum[4][4-1] - prefixSum[4-1][4-1] + arr[4][4]

으로 구할 수 있다.
즉, 녹색부분과 파란 부분의 누적합을 더하고
겹치는 부분은 두번 더해졌으므로 한번 빼주고, 현재 값을 더해주면 된다.

for (int i = 1; i <= r; i++) {
    for (int j = 1; j <= c; j++) {
        prefixSum[i][j] = prefixSum[i-1][j] + prefixSum[i][j-1] - prefixSum[i-1][j-1] + arr[i][j];
    }
}

prefixSum 배열을 추가로 만들지 않고
기존 arr 배열의 값이 이후에 필요없다면 arr에 바로 만들어도 된다.

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

구현 관점

구현에 있어 누적 합을 구현할 때는 인덱스 1번부터 사용하는 것이 훨씬 편하다.
즉, N개의 데이터가 존재할 경우 N+1 크기의 배열을 만든 후
1번부터 N+1번까지의 인덱스를 사용하는게 구현하기 편하다.

📝 직접 풀어보자!

[백준] 11660. 구간 합 구하기 5

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		int[][] sum = new int[N+1][N+1];
		int[][] matrix = new int[N+1][N+1];
		
		
		for(int i = 1; i < N+1; i++) {
			st = new StringTokenizer(br.readLine());
			
			for(int j = 1; j < N+1; j++) {
				matrix[i][j] = Integer.parseInt(st.nextToken());
				sum[i][j] = sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1] + matrix[i][j];
			}
		}
		
		while(M-- > 0) {
			st = new StringTokenizer(br.readLine());
			int x1 = Integer.parseInt(st.nextToken());
			int y1 = Integer.parseInt(st.nextToken());
			int x2 = Integer.parseInt(st.nextToken());
			int y2 = Integer.parseInt(st.nextToken());
			
			int answer = sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1];
			
			System.out.println(answer);
		}
	}

}