해당 포스트는 이지스퍼블리싱, 『알고리즘 코딩테스트 자바 편』, Gene 김종관 을 참고하여 작성하였습니다.

구간 합은 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘입니다. 코딩 테스트에서 사용 빈도가 높으니 꼭 알아 두기 바랍니다.

구간 합의 핵심 이론

구간 합 알고리즘을 활용하려면 먼저 합 배열을 구해야 합니다. 배열 A가 있을 때 합 배열 S는 다음과 같이 정의합니다.

합 배열 S 정의

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

합 배열은 기존의 배열을 전처리한 배열이라 생각하면 됩니다. 이렇게 합 배열을 미리 구해 놓으면 기존 배열의 일정 범위의 합을 구하는 시간 복잡도가 O(N)에서 O(1)로 감소합니다.

합 배열 S를 만드는 공식

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

이렇게 구현한 합 배열을 이용하여 구간 합 역시 쉽게 구할 수 있습니다. i에서 j까지 구간 합을 구하는 공식은 다음과 같습니다.

구간 합을 구하는 공식

s[j] - s[i-1]

정리

구간 합 알고리즘은 배열 또는 리스트와 같은 자료구조에서 주어진 구간의 합을 효율적으로 계산하는 알고리즘입니다. 이 알고리즘은 전처리과정을 통해 구간의 합을 미리 계산하고, 필요할 때마다 이 값을 조회하여 구간의 합을 계산합니다.

1. 전처리 단계

1. 누적 합 배열 생성: 원본 배열의 각 요소까지의 누적 합을 저장하는 배열을 생성합니다.
2. 누적 합 계산: 누적 합 배열을 구합니다. 각 요소는 이전 요소까지의 합을 더한 값이 됩니다.

2. 구간 합 계산 단계

1. 구간 합 계산: 누적 합 배열을 이용하여 주어진 구간의 합을 계산합니다. 구간의 합은 구간의 오른쪽 끝 인덱스의 누적 합에서 구간의 왼쪽 끝 인덱스 바로 이전 인덱스의 누적 합을 빼면 됩니다.

예시 코드

아래는 구간 합을 계산하는 예시 코드입니다.

public class Main {
    // 누적 합 배열을 생성하는 함수
    public static int[] calculatePrefixSum(int[] nums) {
        int n = nums.length;
        int[] prefixSum = new int[n + 1];

        // 누적 합 계산
        for (int i = 1; i <= n; i++) {
            prefixSum[i] = prefixSum[i - 1] + nums[i - 1];
        }

        return prefixSum;
    }

    // 주어진 구간의 합을 계산하는 함수
    public static int calculateRangeSum(int[] prefixSum, int left, int right) {
        // 왼쪽 끝 인덱스 이전의 누적 합과 오른쪽 끝 인덱스의 누적 합을 이용하여 구간 합 계산
        return prefixSum[right + 1] - prefixSum[left];
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5};
        int[] prefixSum = calculatePrefixSum(nums);

        // [1, 3] 구간의 합 계산
        int left = 1;
        int right = 3;
        int rangeSum = calculateRangeSum(prefixSum, left, right);
        System.out.println("구간 합: " + rangeSum); // 출력: 구간 합: 9
    }
}

위 코드에서는 누적 합 배열을 생성하는 calculatePrefixSum 함수와 주어진 구간의 합을 계산하는 calculateRangeSum 함수를 구현하였습니다. calculatePrefixSum 함수를 통해 누적 합을 구하고, 이를 이용하여 주어진 구간의 합을 계산합니다.