누적합(Prefix Sum / Cumulative Sum) 알고리즘

( 누적합 알고리즘 간단 예제 )

[ 1, 2, 3, 4, 5 ] 로 이루어준 숫자 배열에서 각 구간까지의 합을 구하는 배열 [ 1, 3, 6, 10, 15] 을 구한다고 가정해보면 아래와 같이 2가지로 구할 수 있습니다.

[ 첫번째 방법 ] 
1
1+2
1+2+3
1+2+3+4
1+2+3+4+5
식으로 각 인덱스까지의 값을 반복하며 구하기.

[ 두번째 방법 ]
1
1+2
3+3
6+4
10+5
식으로 이전 인덱스까지의 누적합에 현재 인덱스의 값을 더하여 구하기.

2가지 방법을 비교해보면 두 번째 방법이 훨씬 효율적이라는 것을 알 수 있습니다.

이미지 출처 : https://sskl660.tistory.com/77

• 누적 합 이란 수열 An에 대해서 각 인덱스까지의 구간의 합을 구하는 것을 누적 합이라고 합니다.
• 시작점은 항상 첫번째 원소이며, R번째 원소까지의 합을 앞에서부터 쭉 더해오는 패턴입니다.
• 모든 구간에 대해서 처음부터 계산하여 단순 반복하는 것이 아니라 이전 인덱스까지의 누적합에 현재 자기 자신 값을 더하여 구현하는 것이 효과적인 방법입니다.

그렇다면 어떠한 경우에 효과적으로 누적합 알고리즘을 적용시킬 수 있을까요?

 

=> 배열의 [ A ~ B ] 범위의 구간 합을 구하고자 할 때, 누적합 배열을 구한 후 B 까지의 누적합에서 A-1까지의 누적합을 빼주면 [ A ~ B] 범위의 구간의 합을 구할 수 있습니다. 

 

2. 문제 풀이 

   2 - 1) 백준 11659번 : 구간 합 구하기 4

11659번: 구간 합 구하기 4

function solution(input) {

    let answer = [];
    let [N, K] = input.shift().split(' ').map((dr) => Number(dr)); 
    let matrix = input.shift().split(' ').map((dr) => Number(dr)); // 주어진 수열

    // N + 1 하는 이유 => 인덱스로 접근하지 않고 순서로 접근하기 위해
    let prefixSum = Array.from({ length: N + 1 }).fill(0);

    // 누적합 구하기
    for (let i = 0; i < N; i++) {
        // 현재 인덱스 까지의 누적값 = 이전 인덱스의 누적값 + 현재 인덱스의 원소 값
        // 순서로 접근하기 위해 1부터 넣어줌
        prefixSum[i + 1] = prefixSum[i] + matrix[i];
    }

    for (let i = 0; i < input.length; i++) {

        let [start, end] = input[i].split(' ').map((dr) => Number(dr));

        answer.push(
            // end까지 누적합에서 start-1까지 누적합을 빼주면 start ~ end 까지의 구간의 합과 같음
            prefixSum[end] - prefixSum[start - 1]
        );

    }

    return answer.join('\n')
}

// '/dev/stdin'
const input = require('fs').readFileSync('stdin').toString().trim().split('\n');
console.log(solution(input));

• 인덱스가 아닌 순서로 접근하기 위해 누적합의 배열을 주어진 수열의 크기보다 +1 크게 만듭니다.
• 누적합을 계산하여 누적합 배열에 넣어줍니다.
• 구간합은 end까지의 누적합에서 start-1 위치의 누적합을 빼주면 구할 수 있습니다. 

 

   2 - 2) 백준 11660번 : 구간 합 구하기 5

11660번: 구간 합 구하기 5

function solution(input) {
    let answer = [];
    let set = input.shift().split(' ');
    let N = Number(set[0]); // 행렬의 크기
    let M = Number(set[1]); // 구간합 구해야할 구간
    let matrix = Array.from(Array(N + 1), () => Array(N + 1).fill(0)); // N*N 크기의 행렬 초기화

    // matrix 채워주기 - 누적합으로!
    for (let i = 1; i <= N; i++) {
        let curRow = input.shift().split(' ').map((dr) => Number(dr));

        for (let j = 1; j <= curRow.length; j++) {
            matrix[i][j] =
                (matrix[i - 1][j] || 0)
                + (matrix[i][j - 1] || 0)
                - (matrix[i - 1][j - 1] || 0) // 겹치는 부분 빼주고
                + curRow[j - 1]; // 자기 자신 더해주고
        }
    }

    for (let i = 0; i < input.length; i++) {
        let curRow = input[i].split(' ').map((dr) => Number(dr));

        let p1 = [curRow[0], curRow[1]];
        let p2 = [curRow[2], curRow[3]];

        let m_p1 = [p1[0] - 1, p2[1]]; // 빼야할 위치의 좌표1
        let m_p2 = [p2[0], p1[1] - 1]; // 빼야할 위치의 좌표2
        let overap_p3 = [Math.min(m_p1[0], m_p2[0]), Math.min(m_p1[1], m_p2[1])]; // 겹치는 부분의 좌표

        answer.push(
            matrix[p2[0]][p2[1]]
            - matrix[m_p1[0]][m_p1[1]]
            - matrix[m_p2[0]][m_p2[1]]
            + matrix[overap_p3[0]][overap_p3[1]] // 겹치는 부분은 2번 빼줬으므로 한번 더해주기
        );
    }

    return answer.join('\n')
}

// '/dev/stdin'
const input = require('fs').readFileSync('stdin').toString().trim().split('\n');
console.log(solution(input));

문제를 푼 원리 1번

문제를 푼 원리 2번

• 먼저 각 좌표에서 좌표끼리의 누적합을 구합니다. (누적합을 구할 때는 겹치는 부분은 2번 더해지기 때문에 한 번씩 빼줘야 합니다. - 이미지 1번 참고)
• 좌표 구간끼리 구간합을 구하기 위해서는 먼저 (1,1) ~ (큰 좌표)까지의 누적합에서 (1,1) ~ (큰 좌표) 좌표 구간에 포함하고 있지 않은 부분의 구간합을 빼줍니다. (겹치는 부분은 2번 빼주기 때문에 한번 더해줘야 합니다. - 이미지 2번 참고, 빨간색 네모 친 부분이 큰 좌표까지 구간에서 포함하고 있지 않은 부분이라 빼준 부분입니다. 또한 빨간색 배경으로 색칠한 부분은 2번 빼주기 때문에 한번 더해줬습니다.)

 

 

누적합 알고리즘을 바탕으로 푸는 변형 문제가 많으니 충분히 이해하고 넘어가자~