[알고리즘] 누적합 prefix sum

누적합?

누적 합(prefix sum) 알고리즘은 계산양을 줄여서 시간적으로 많은 이득을 볼 수 있는 알고리즘 입니다.

 

 

예를 들어

1.그냥 더하기

arr[0]~arr[5]까지 입력을 받은 후,

arr[0]부터 arr[5]까지 합을 구해야 될때 5번 더하기를 해야 합니다.

 

2.누적합 이용

누적합을 이용하면

arr[0]~arr[5]에 각각 누적합을 더해서 넣어 줍니다.

그 후에,

arr[0]부터 arr[5]까지 합을 구하려면 따로 연산없이 바로 바로 불러 올 수 있습니다.

arr[0]~arr[5]의 합은 arr[5]

또한 arr[2]~arr[5]의 값 또한 arr[5] - arr[1]계산 1번을 통해 구할 수 있습니다.

 

 

얼핏 보면 시간차가 별로 안날 수도 있다고 생각할 수도 있지만,

ex)

배열 수가 매우 많아져 arr[0]~arr[10000]이 있다고 할때

arr[2]~arr[5]의 합은?

arr[5]~arr[3241]의 합은?

arr[2]~arr[2321]의 합은?

arr[3]~arr[9999]의 합은?

arr[2341]~arr[9874]의 합은?

1번 방법은 매우 많은 계산을 해야합니다.

그러나 2번 방법은 문제당 계산 1번씩만 하면 됩니다.

(물론 누적합을 만드는 계산은 해야 하지만)

 

<입력받으면서 누적합 배열 만들기>

int map[][] = new int[N][N];
	    for(int i=0; i<N; i++) {
	    	st = new StringTokenizer(br.readLine());
	    	for(int j=0; j<N; j++) {
	    		map[i][j] = Integer.parseInt(st.nextToken());
	    		if(j >= 1) {
	    			map[i][j] = map[i][j] + map[i][j-1];
	    		}
	    	}
	    }