알고리즘 - 누적합

누적합

---

누적합(Cumulative Sum)은 배열이나 리스트의 특정 구간 합을 빠르게 계산하기 위해 사용하는 알고리즘 기법이다. 일반적으로 대량의 데이터에서 특정 구간의 합을 반복적으로 구해야 하는 경우, 단순히 반복문을 이용해 매번 합을 계산하는 것은 비효율적일 수 있다. 이때, 누적합 배열을 활용하면 원하는 구간의 합을 상수 시간 내에 구할 수 있다.

 

누적합의 원리

---

누적합의 기본 원리는 배열의 각 위치까지의 값을 순차적으로 더해 새로운 배열을 생성하는 것이다. 이를 통해 배열의 특정 구간 합을 빠르게 계산할 수 있다. 예를 들어, 배열의 i번째 위치까지의 누적합은 원본 배열의 0번째 인덱스부터 i번째 인덱스까지의 합을 저장하는 형태다.

누적합 배열을 S라고 할 때, 원본 배열 A에서 구간 [i, j]의 합은 다음과 같은 공식으로 계산된다: 구간 합=S[j]−S[i−1] 이 공식의 원리는 i번째 인덱스까지의 누적합에서 j번째 인덱스까지의 누적합을 빼면, i에서 j 구간의 합만 남는다는 점에 기반한다.

 

 

누적합 시간복잡도

---

누적합을 사용하지 않고 매번 구간 합을 구한다면 구간 합 계산의 시간 복잡도는 O(n)이 된다. 하지만 누적합을 활용하면 사전 작업을 통해 누적합 배열을 생성하는 데 O(n)의 시간이 소요되며, 이후 각 구간 합을 O(1)로 빠르게 계산할 수 있다. 이는 특히 여러 구간 합을 반복적으로 계산해야 하는 상황에서 효율성을 극대화할 수 있는 방법이다.

 

 

누적합 예시

---

누적합의 예제를 통해 실제로 어떻게 적용되는지 살펴보자. 다음은 간단한 배열을 사용해 누적합 배열을 만드는 과정과 구간 합을 구하는 방법이다.

간단한 배열에서의 누적합

원본 배열 A = [2, 4, 6, 8, 10]이 있을 때, 누적합 배열 S를 생성하는 과정은 다음과 같다:

1. S[0]=A[0]=2
2. S[1]=S[0]+A[1]=2+4=6
3. S[2]=S[1]+A[2]=6+6=12
4. S[3]=S[2]+A[3]=12+8=20
5. S[4]=S[3]+A[4]=20+10=30

따라서 누적합 배열 S는 [2, 6, 12, 20, 30]이 된다.

 

구간 합 구하기

이제 배열 A에서 구간 [1, 3]의 합을 구하고자 한다. 즉, A[1]부터 A[3]까지의 합을 계산하는 것이다. 이를 누적합 배열 S를 이용해 빠르게 구할 수 있다.

1. 누적합 배열에서 S[3] = 20이고, S[0] = 2이다.
2. 구간 합은 S[3] - S[0] = 20 - 2 = 18이 된다.

따라서 배열 A의 [1, 3] 구간의 합은 18이다.

 

public class CumulativeSumExample {

    public static void main(String[] args) {
        // 원본 배열
        int[] A = {2, 4, 6, 8, 10};
        
        // 누적합 배열 초기화
        int[] S = new int[A.length + 1];
        
        // 누적합 배열 생성
        for (int i = 1; i <= A.length; i++) {
            S[i] = S[i - 1] + A[i - 1];
        }

        // 구간 [1, 3]의 합 계산
        int start = 1;
        int end = 3;
        System.out.println("구간 [1, 3]의 합: " + rangeSum(S, start, end));  // 출력: 구간 [1, 3]의 합: 18
    }

    // 구간 합 계산 함수
    public static int rangeSum(int[] S, int start, int end) {
        return S[end + 1] - S[start];
    }
}

 

위 코드에서 range_sum 함수는 시작 인덱스와 끝 인덱스를 인수로 받아 해당 구간의 합을 계산하여 반환한다. S[end + 1] - S[start]로 구간 합을 구함으로써, 누적합 배열을 이용해 O(1)의 시간 복잡도로 구간 합을 계산한다.

 

다음은 직접 풀이한 BOJ 누적합 문제다.

 

public class 누적합 {
    static int n,m;
    static int[] arr;
    static int[] sum;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        arr = new int[n+1];
        sum = new int[m];
        st = new StringTokenizer(br.readLine());
        arr[0] = 0;
        for (int i = 1; i <= n; i++) {
            arr[i] = arr[i-1] + Integer.parseInt(st.nextToken());
        }

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            sum[i] = arr[y] - arr[x-1];
            bw.write(sum[i] + "\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }
}