[알고리즘] 구간 합 알고리즘

구간 합

구간 합은 배열에 특정 구간에서의 값을 합을 말한다.
예를 들어 1 ~ 5까지의 배열이 있다고 하자.
여기서 두 번째부터 네 번째까지의 합을 구해보자.
두 번째, 세 번째, 네 번째의 갑을 더하면 된다.
즉, 2, 3, 4를 더한 값이고 9가 답이 될 것이다.

위 내용을 배열 A와 기호로 표현을 해보자
A = [1, 2, 3, 4, 5] 의 배열이 있다.
구간 합을 S라고 할 때, S = A[1] + A[2] + A[3]이 된다.

합 배열

구간 합 알고리즘을 사용하기 위핵서는 합 배열을 구해줘야 한다.

합 배열은 첫 번째 값부터 특정 인덱스까지의 누적 합의 배열이다.
예를 들어 A = [1, 2, 3, 4, 5]가 있을 때, 합 배열을 S라고 한다면 S = [1, 3, 6, 10, 15] 이다.
각 값들을 순서 대로 더하는데 이 더한 값을 누적해서 배열로 만든 것이다.
이 합 배열을 구하는 공식은

S[i] = S[i-1] + A[i]이다.

만약 S[3] 구하고자 한다면 배열 A의 인덱스 0부터 3까지의 값을 더하는 것이다.
위 공식에 대입을 한다면 S[3] = S[2] + A[3]이다.

이를 풀어서 보자면 S[2]는 배열 A에 인덱스 0부터 2까지 더한 값이다.
여기서 배열 A에 인덱스 3의 값을 더한다면 배열 A의 인덱스 0부터 3까지 더한 값이다.
이는 우리가 구하고자 하는 S[3]의 값이다.

이 합 배열을 코드로 알아보자

int[] arr = {12, 45, 4, 10, 21};
int[] sumArray = new int[arr.length];

for (int i = 0; i <= arr.length; i++) {
	if (i == 0) {
    	sumArray[i] = arr[i];
    } else {
    	sumArray[i] = sumArray[i - 1] + arr[i];
    }
}

arr이라는 배열이 있고 그 크기 만큼의 합 배열을 만들어 준다.
그리고 arr을 반복을 통해서 합 배열 만들어준다.
이 때, S[0]은 이전의 인덱스 값이 없기 때문에 arr 배열에 인덱스 0의 값을 넣어준다.
그리고 그 이후의 합 배열의 값은 합 배열의 이전 값에 arr의 배열의 값을 더해주면서 값을 구해준다.
우리가 위에서 살펴본 합 배열 공식을 통해서 합 배열을 구할 수 있다.

구간 합 알고리즘

이제 이 합 배열을 통해서 구간 합 알고리즘을 알아보자.
구간 합 알고리즘은 구간 합을 빠르게 구하는 알고리즘이다.

이 구간 합의 공식은 합 배열 S가 있고 i에서 j까지 구간 합을 구할 때,

S[j] - S[i-1]

이라는 공식을 가진다.

어떻게 이러한 공식을 가지는지 알아보자.

A라는 배열이 있다.
우리는 A 배열에서 인덱스 값 2부터 3까지의 구간 합을 구하고 싶다.
먼저, 인덱스 값 3까지의 누적합을 구한다.
그리고 인덱스 값 2의 전 값인 1의 누적 합을 빼주면 인덱스 2에서 3까지의 구간 합이 나온다.
위 그림에서 보면 검은 색의 화살표에서 빨간 색의 화살표를 뺀 것이다.

이를 위 공식에 대입을 해보자

합 배열 S와 i는 2, j는 3이다.
구간 합은 A[2]+A[3]이다.

이는

S[3] = A[0]+A[1]+A[2]+A[3]
S[1] = A[0]+A[2]

S[3] - S[1] = A[2] + A[3]
을 나타낸다.

위 예시를 보면
S[j] - S[i-1]을 통해서 구간 합을 빠르게 구할 수 있다.

코드를 살펴보자

int[] arr = {12, 45, 4, 10, 21};
int[] sumArray = new int[arr.length];

int i = 1;
int j = 3;

for (int i = 0; i <= arr.length; i++) {
	if (i == 0) {
    	sumArray[i] = arr[i];
    } else {
    	sumArray[i] = sumArray[i - 1] + arr[i];
    }
}

System.out.println(sumArray[j] - sumArray[i - 1]);

기존의 합 배열을 구하는 코드에서 i와 j를 통해서 구간 합을 구하는 코드이다.
합 배열 sumArray에 j인덱스 값에서 i인덱스의 -1를 한 값을 빼준다.
이 부분이 우리가 위에서 살펴본 구간 합을 구하는 공식이다.
이 구간 합 공식을 통해서 구간 합을 알고리즘을 만들면 구간 합을 빠르게 구할 수 있다.