[Java] 구간 합 구하기 (자바 | Java)

[Java] 구간 합 구하기

---

구간 합

구간 합?

구간 합은 합 배열을 이용하여 구하는 알고리즘이다.

구간 합과 합 배열

구간 합을 활용하기 위해선 먼저 합 배열을 구해야 한다. 배열 A가 있을 때
합 배열 S는 다음과 같이 정의 된다.

A[0]부터 A[i]까지의 합 S
S[i] = A[0] + A[1] + A[2] + ... + A[i - 1] + A[i]

이렇게 합 배열을 미리 구해놓으면 기존 배열의 일정 범위의 합을 구하는 시간 복잡도가
O(N)에서 O(1)로 감소한다. 그림을 통해 보면 다음과 같다.

위 표를 보면 다음과 같이 간단한 공식을 만들 수 있다.

S[i] = S[i - 1] + A[i]

이를 통해 구간 합을 구하는 공식은 다음과 같다.

i에서 j까지의 구간 합
S[j] - S[i - 1]

구현

구현은 매우 쉽다. 위의 표를 예로 들면 코드는 다음과 같다.

public class Main {
    public static void main(String[] args) {
        int[] arr = {15, 13, 10, 7, 3, 12};
        int[] sumArr = new int[arr.length];
        sumArr[0] = arr[0];

        // 합 배열 S[i] = S[i - 1] + A[i]
        for (int i = 1; i < arr.length; i++) {
            sumArr[i] = sumArr[i - 1] + arr[i];
            System.out.print(sumArr[i] + " ");
        }
        System.out.println();

        // 구간 합 구하기 S[j] - S[i - 1] ex ) arr[2] ~ arr[5]
        int i = 2;
        int j = 5;
        System.out.println("구간 합 알고리즘 : " + (sumArr[j] - sumArr[i - 1]));

        // 직접 구하기
        int result = 0;
        for (int k = 2; k < arr.length; k++) {
            result += arr[k];
        }
        System.out.println("직접 구하기 : " + result);
    }
}
---------------output---------------
28 38 45 48 60 
구간 합 알고리즘 : 32
직접 구하기 : 32