누적합과 구간합

목적

최근에 모르는 알고리즘을 공부하있는데 몇일을 봐도 이 알고리즘이 이해가 않돼서 정리하고 나중에 내가 까먹었을때를 대비해서 설명하려고 한다.

누적합(Prefix Sum, Cumulative Sum)
누적합이란 나열된 수의 누적된 합을 말한다. 수열 An에 대해서 구간[1, 1]의 합, 구간[1, 2]의 합, 구간[1, 3]의 합, ..., [1, n]의 합을 누적 합이라고 한다.

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

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

구간 합(Range Sum)
구간 합은 배열이나 리스트의 연속된 부분 집합의 합을 의미한다.

누적 합의 사용
누적합은 목적에 따라 다양한 문제에 활용이 가느하다. 대표적으로 누적 합을 사용하는 문제는 카운딩 정렬(Counting Sort), 구간 합 구하기가 존재한다.

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

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
15
37

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

이렇게 모든 입력마다 구가합을 구하는 경우에는 구간의 길이가 M이라고 하면 매 구간합을 구할때 마다 O(M)이라는 시간이 걸린다. N개의 구간의 길이가 M인 구간합을 구하는 경우 O(NM)의 시간이 걸리는 것을 알 수 있다.

누적 합을 이용한 구간 합 구하기
문제를 개선하기 위해 누적 합을 이용하여 구간 합을 구하는 방법을 사용한다면, 시간 복잡도를 O(N + M)까지 줄일 수 있다. 일반적으로 수열 An에서 구간[i, j]까지의 구간 합을 구하는 경우를 생각해봐라.

그림과 같이 n항 까지의 합을 Sn이라고 정의한다면, 구간 [i, j]의 구간합은 Sj와 Si-1을 뺀 값을 구하여 바로 구할 수 있다. 즉, Sn까지의 구간합을 모두 구해 놓기만 한다면(O(M)) 구간 합을 구하는 연산 자체는 O(1)의 시간이면 구할 수 있기 때문에 결론적으로 O(N + M)의 시간 복잡도를 갖는 구간 합을 구하는 연산을 만들 수 있다. 누적 합을 구하고, 그 누적합을 이용하여 주어진 구간의 합을 구하는 로직을 이용하여 구간 합을 더 빠르게 계산할 수 있다. 아래는 위와 같은 입력 값을 바탕으로 누적 합을 이용한 구간 합을 구하는 로직을 구현해 보았다.

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();
	}
}

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

마무리

알고리즘에 대해서 생각을 해봤지만 아무래도 스스로 느끼기에는 조금 어려운것같다. 그래서 내일 모레 계속 관련개념을 봐야할것같다.