5. 누적 합 (Prefix Sums) Codility Lesson 한국어 정리본 (JavaScript ver.)

누적 합(Prefix Sums)이란?

배열의 특정 구간(슬라이스)의 합을 빠르게 계산하는 강력한 기법이 누적 합(Prefix Sums) 이다. 이는 배열의 처음부터 특정 위치까지의 합을 미리 계산해 저장하는 방법이다.

예를 들어, 배열 A가 다음과 같다고 하자.

A = [a₀, a₁, a₂, ..., aₙ₋₁]

그러면 누적 합 배열 P는 다음과 같이 정의된다.

P[0] = 0
P[1] = a₀
P[2] = a₀ + a₁
P[3] = a₀ + a₁ + a₂
...
P[n] = a₀ + a₁ + ... + aₙ₋₁

이전 값 P[k-1]에 현재 값 A[k-1]을 더하는 방식으로 누적 합을 계산할 수 있으며, 전체 연산은 O(n) 의 시간 복잡도를 가진다.

---

1. O(n) 시간 복잡도의 누적 합 계산

JavaScript 코드:

function prefixSums(A) {
    let n = A.length;
    let P = new Array(n + 1).fill(0);
    for (let k = 1; k <= n; k++) {
        P[k] = P[k - 1] + A[k - 1];
    }
    return P;
}

이 함수는 입력 배열 A의 누적 합을 계산하여 반환한다.

---

2. O(1) 시간 복잡도의 구간 합 계산

누적 합을 활용하면 특정 구간 [x..y]의 합을 O(1) 만에 구할 수 있다.

구간 합: P[y + 1] - P[x]

JavaScript 코드:

function countTotal(P, x, y) {
    return P[y + 1] - P[x];
}

이 방법을 사용하면 O(n + m) 시간 복잡도로 여러 개의 구간 합을 빠르게 계산할 수 있다.

---

3. 버섯 줍기 문제

도로 위 특정 위치 k에서 시작하여 최대 m번 이동하면서 버섯을 최대한 많이 수집하는 문제이다. 이동은 인접한 위치로만 가능하다.

O(n²) (비효율적인 방법)

function slowMushrooms(A, k, m) {
    let n = A.length;
    let result = 0;
    for (let p = 0; p <= m; p++) {
        let left = k - p;
        let right = Math.min(n - 1, k + (m - 2 * p));
        let sum = 0;
        for (let i = left; i <= right; i++) {
            sum += A[i];
        }
        result = Math.max(result, sum);
    }
    return result;
}

이 방법은 O(m²) 시간이 소요된다.

---

O(n + m) (효율적인 방법)

누적 합을 이용하여 O(n + m) 시간 복잡도로 문제를 해결할 수 있다.

function mushrooms(A, k, m) {
    let n = A.length;
    let result = 0;
    let P = prefixSums(A);
    
    for (let p = 0; p <= Math.min(m, k); p++) {
        let left = k - p;
        let right = Math.min(n - 1, Math.max(k, k + m - 2 * p));
        result = Math.max(result, countTotal(P, left, right));
    }
    
    for (let p = 0; p <= Math.min(m, n - k - 1); p++) {
        let right = k + p;
        let left = Math.max(0, Math.min(k, k - (m - 2 * p)));
        result = Math.max(result, countTotal(P, left, right));
    }
    
    return result;
}

이 방법은 누적 합을 활용하여 슬라이스 합을 O(1)에 계산하므로 전체 연산을 O(n + m) 시간 복잡도로 수행할 수 있다.