Cumulative Sum

누적 합은 배열 A가 주어졌을 때 0 ~ N번째 까지 탐색하며 각 인덱스 번째 까지의 합을 구하는 알고리즘이다.

  • [1,2,3,4,5]이라는 배열이 주어졌을 때
  • 누적합은 [1,3,6,10,15]가 된다.

구간합 - Prefix Sum

이렇게 각 인덱스 마다 합계를 구해두는 누적합을 이용하면 시간 복잡도를 줄일 수 있다. 만약 2~4(0부터 시작)번째 인덱스의 합을 구한다 하였을 때 4번째 누적합 15에서 1번째 값인 3을 빼면 된다. 15 - 3 = 12;

예시 문제

백준 [꿀 아르바이트]

누적 합을 이용한 예시 문제이다. 구간의 합을 구해야 하는데 다른 복잡하게 응용할 것 없이 구간 합으로 어렵지 않게 문제를 풀 수 있다.

class Main {
    public static long prefixSum(long[] cumSum, int n, int m) {
        long result = 0;

        for (int i = m; i < n + 1; i++) {
            result = Math.max(result, cumSum[i] - cumSum[i - m]);
        }

        return result;
    }

    public static long[] cumSum(int[] arr) {
        long[] cumSum = new long[arr.length + 1];
        long sum = 0;
        for (int i = 1; i < cumSum.length; i++) {
            cumSum[i] = arr[i - 1] + cumSum[i - 1];
        }

        return cumSum;
    }
}
  • cumSum에서 각 인덱스일 때 누적 합을 구한다.
  • prefixSum에서 주어진 조건으로 계산한 구간 합 중에서 가장 큰 값을 반환한다.

백준 예시

5 3
10 20 30 20 10
  • 누적 합을 구하면 [0, 10, 30, 60, 80, 90]
  • 누적 합에서는 보통 배열의 길이를 하나 크게 만들어서 사용한다. 인덱스가 0부터 시작하는 배열에서 0번 째를 비워두고 1부터 시작하는 것이다. 인덱스를 신경 쓰지 않아도 되기 때문에 좀 더 편해진다.
  • 이 문제는 슬라이딩 윈도우로도 풀 수 있다.

prefixSum 안에 for문

  1. result = 60 - 0
  2. result = 80 - 10
  3. result = 90 - 30