[Java]누적 합(Prefix Sum , Cumulative Sum)

*누적 합(Prefix Sum, Cumulative Sum)

-> 누적 합이란, 말 그대로 나열된 수의 누적된 합을 말한다.

-> 조금 더 엄밀히 말하면, 수열 An에 대해서, 구간 [1, 1]의 합, 구간 [1, 2]의 합, 구간 [1, 3]의 합, ..., [1, n]의 합을 누적 합이라고 한다.

자연수를 나타내는 수열 An의 5항까지의 누적 합

※ 따라서 Prefix Sum의 각 요소는 해당 해당 인덱스까지의 부분 합(Partial Sum)을 의미한다. 부분 합은 급수에서 말하는 그 부분합의 의미가 맞다.

 

*누적 합의 사용

-> 누적 합은 그 목적에 따라 다양한 문제에 활용이 가능하다.

-> 대표적으로 누적 합을 사용하는 문제는 카운팅 정렬(Counting Sort), 구간 합 구하기가 존재한다.

 

*단순 반복을 이용한 구간 합 구하기

-> 이 글의 핵심 목적이다. 일반적으로 구간의 합을 구하는 경우에는 다음과 같이 모든 구간의 값을 더해주는 방법을 생각해볼 수 있다.

import java.util.Scanner;

public class PrefixSum {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
		int[] arr2 = {1, 5, 8, 10, 24, 3, 5, 100, 99, 7};
		int a = sc.nextInt();
		int b = sc.nextInt();
		int sum1 = 0;
		int sum2 = 0;
		for(int i = a; i <= b; i++) {
			sum1 += arr[i];
			sum2 += arr2[i];
		}
		System.out.println(sum1);
		System.out.println(sum2);
		sc.close();
	}
}

3번 ~ 5번 인덱스의 구간합

 하지만 이렇게 모든 입력마다 구간합을 일일히 구해주는 경우에는 구간의 길이가 M이라고 하면 매 구간합을 구할 때 마다 O(M)이라는 시간이 걸리게 된다. 즉, N개의 구간 에 대해 구간의 길이가 M인 구간합을 구하는 경우 O(NM)의 시간이 걸리는 것을 알 수 있다.

 예를 들어, 자연수 구간 [1, 200,000]에서 각 자연수를 시작점으로 구간의 길이가 10000인 구간합을 모두 구하라는 문제를 생각해보면 해당 연산을 바탕으로 모든 구간합을 구하는 경우 총 20억번 가량의 연산을 진행하여야 한다.

 

*누적 합을 이용한 구간 합 구하기

-> 이러한 문제를 개선하기 위해 누적 합을 이용하여 구간 합을 구하는 방법을 사용한다면, 시간 복잡도를 O(N + M)까지 줄일 수 있다. 이 방법은 수열의 부분 합 관련 문제를 풀 때 많이 사용하던 아이디어를 가져오면 된다.

-> 일반적으로 수열 An에서 구간 [i, j]까지의 구간 합을 구하는 경우를 생각해보자.

 그림과 같이 n항 까지의 합을 Sn이라고 정의한다면, 구간 [i, j]의 구간합은 Sj와 Si-1을 뺀 값을 구하여 바로 구할 수 있다. 즉, Sn까지의 구간합을 모두 구해 놓기만 한다면(O(M)) 구간 합을 구하는 연산 자체는 O(1)의 시간이면 구할 수 있기 때문에 결론적으로 O(N + M)의 시간 복잡도를 갖는 구간 합을 구하는 연산을 만들 수 있다.

-> 결론적으로 누적 합을 구하고, 그 누적합을 이용하여 주어진 구간의 합을 구하는 로직을 이용하여 구간 합을 더 빠르게 계산할 수 있다. 아래는 위와 같은 입력 값을 바탕으로 누적 합을 이용한 구간 합을 구하는 로직을 구현해 보았다.

import java.util.Scanner;

public class PrefixSum {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
		int[] arr2 = { 1, 5, 8, 10, 24, 3, 5, 100, 99, 7 };
		int a = sc.nextInt();
		int b = sc.nextInt();

		// 누적 합 구하기
		// 배열의 크기를 + 1하는 이유는, 0번 인덱스 ~ n번 인덱스의 구간합도 구할 수 있게 만들기 위함이다.
		int[] prefix_sum = new int[11];
		int[] prefix_sum2 = new int[11];
		for (int i = 1; i < arr.length; i++) {
			prefix_sum[i] += prefix_sum[i - 1] + arr[i];
			prefix_sum2[i] += prefix_sum2[i - 1] + arr2[i];
		}
		
		// 구간 합 구하기
		System.out.println(prefix_sum[b] - prefix_sum[a - 1]);
		System.out.println(prefix_sum2[b] - prefix_sum2[a - 1]);
		sc.close();
	}
}

3번 ~ 5번 인덱스의 구간합

※ 주석에도 언급해 두었지만, 0번째 인덱스 ~ n번째 인덱스의 구간 합도 구할 수 있게 만들기 위해서는 배열의 크기를 하나 늘려서 앞에 0이라는 값을 추가해주어야 0번째 인덱스에 대한 구간 합도 구할 수 있다.