[알고리즘] 누적합, 구간합 구하기

누적합(Prefix Sum)과 구간합

누적합

누적합이란 나열 된 수들의 누적된 합을 뜻합니다.

즉, 이 배열의 누적합을 구하면 1 + 3 + 4 + 2 + 5 = 15가 됩니다.

누적합의 배열의 크기가 원본 배열보다 1더 큰데 이는 밑에서 설명하겠습니다.

 

구간합

말 그대로 나열 된 수 중에서 합을 구하고 싶은 구간의 합입니다.

만약 1번째 인덱스부터 ~ 3번째 인덱스까지의 구간합을 구한다면, 3 + 4 + 2 = 11이 됩니다.

 

구간합을 빠르게 구할 수 있는 공식이 있는데, 이 공식이 만들어지는 과정을 봅시다.

누적합 배열 prefixSum의 크기가 arr보다 1 더 큰 이유는 0번 인덱스 부터 n번 인덱스의 구간합을 구할 수 있게 하기 위함입니다.

 

이제 1번째 인덱스부터 ~ 3번째 인덱스까지의 구간합을 구한다면, 

누적합을 가진 배열을 구하고 그 누적합 배열의 4번째 인덱스와 1번째 인덱스를 뺀 값과 같습니다.

즉, prefixSum[b] - prefixSum[a - 1] 가 됩니다.

 

❗ 주의할점

prefixSum의 배열은 arr보다 1더 크기 때문에 구하고자 하는 구간의 인덱스를 입력하는게 아니라

구하고자 하는 구간의 수가 몇 번째인지 입력해야합니다.

아래 코드를 본다면 이해가 가실 겁니다.

 

---

코드

import java.util.Arrays;
import java.util.Scanner;

public class 누적합 {
    public static void main(String[] args) {
        int[] arr1 = {1, 3, 4, 2, 5};
        int[] prefixSum = new int[arr1.length + 1];
        int sum = 0;

        for (int i = 0; i < arr1.length; i++) {
            sum += arr1[i];
            prefixSum[i + 1] = sum;
        }

        System.out.println("합을 구할 배열 : " + Arrays.toString(arr1));
        System.out.println("총합 : " + sum);
        System.out.println("누적합의 배열 : "+ Arrays.toString(prefixSum));
        System.out.println("=================================");

        // 구간합
        Scanner input = new Scanner(System.in);
        System.out.println("구간 합을 시작할 구간을 입력해주세요. : ");
        int a = input.nextInt();
        System.out.println("구간 합을 끝낼 구간을 입력해주세요. : ");
        int b = input.nextInt();

        System.out.print("누적합 결과 : ");
        System.out.println(prefixSum[b] - prefixSum[a - 1]);
    }
}