누적합 알고리즘

배열 또는 리스트에서 특정 구간의 합을 빠르게 계산하거나, 데이터를 누적하여 처리하기 위해 사용하는 알고리즘 주어진 배열 arr에서 누적합 배열 prefixSum은 각 위치까지의 합을 저장한 배열이다.
prefixSum[i] = arr[0] + arr[1] + ... + arr[i - 1] + arr[i]

접근 방법

• 배열의 값을 누적하여 새로운 배열을 생성한다.
• 누적합 배열을 사용하면 구간 합이나 누적 데이터를 효율적으로 계산할 수 있다.

1차원 배열

1	2	1	4	1	1

위와 같은 표가 있다고 가정했을 때 아래와 같이 합을 구한다고 주어진다면

1. (0 ~ 3) 범위에 3을 더한다.
2. (1 ~ 4) 범위에 4를 뺀다.

위의 배열에 직접 더하는 것이 아니라 별도로 누적합을 위한 배열을 만든다.

0	0	0	0	0	0

1번의 요구사항에 맞춘 배열은 아래와 같다.

3	0	0	0	-3	0

2번의 요구사항에 맞춘 누적합 배열은 아래와 같다.

0	-4	0	0	0	4

누적합은 두 개의 배열을 아래와 같이 합칠 수 있다.

3	-4	0	0	-3	4

이렇게 정리한 누적합 배열을 더하면 아래와 같이 결과가 나오게 된다. 앞의 값에서 부터 오른쪽 배열을 값을 하나씩 더해가면 된다.

3	-1	-1	-1	-4	0

이후 원본 배열을 위의 결과 배열과 합치면 원하는 결과가 나오게 된다.

3	-1	-1	-1	-4	0
1	2	1	4	1	1
4	1	0	3	-3	1

2차원 배열

풀었던 문제

접근 방법

원본 배열이 존재하고 들어오는 입력에 맞춰서 배열의 값을 더하거나 마이너스를 해야 한다. 들어오는 입력마다 원본 배열을 변환해 줘도 되지만 입력값의 길이를(1000 * 1000 * 250000) 확인해 봤을 때 효율성 테스트는 불가능 하다고 판단 되어서 다른 방법을 찾아보았고 위에서 찾은 누적합이라는 개념을 적용하고자 하였다. 2차원 배열은 더하는 방향이 좌우로 한 번 상하로 한 번 진행을 하게 된다.

예시

만약 (1 ~ 1) 부터 (3 ~ 3) 까지 5를 더해줘야 한다면 아래와 같이 배열로 표시할 수 있다.

0	0	0	0	0
0	5	0	0	-5
0	0	0	0	0
0	0	0	0	0
0	-5	0	0	5

여기서 누적합을 진행하는 방식은 좌우로 한 번 상하로 한 번 진행하면 된다.

1. Row를 하나씩 확인해서 왼쪽에서 오른쪽으로 합을 진행한다.

0	0	0	0	0
0	5	5	5	0
0	0	0	0	0
0	0	0	0	0
0	-5	-5	-5	0

2. Col을 하나씩 확인해서 위에서 아래로 합을 진행한다.

0	0	0	0	0
0	5	5	5	0
0	5	5	5	0
0	5	5	5	0
0	0	0	0	0

이후 원본 배열과 결과가 나온 누적합 배열을 합치면 된다.

주의사항

누적합 배열을 생성할 때 마지막 인덱스의 경우 주어진 배열보다 하나 더 큰 인덱스에 반대 값을 주므로
항상 하나 더 큰 인덱스의 배열로 누적합 배열을 준비해야 한다.

작성한 문제 풀이

아래와 같이 누적합을 위한 배열을 만들어준다.

// 누적합 용 배열은 인덱스를 하나 더 크게 (주의)
dp = new int[board.length + 1][board[0].length + 1];  
  
for (int[] ski : skill) {  
    int gizun = ski[0];  
  
    int damage = gizun == 1 ? (ski[5] * -1) : ski[5];  
  
    int row = ski[1];  
    int col = ski[2];  
    int endRow = ski[3] + 1;  
    int endCol = ski[4] + 1;  
  
    dp[row][col] += damage;  
    dp[endRow][endCol] += damage;  
    dp[row][endCol] += (damage * (-1));  
    dp[endRow][col] += (damage * (-1));  
  
}

왼 오른쪽 방향으로 합산을 진행

public void rowDirSum() {  
    for (int row = 0; row < dp.length; row++) {  
        int sum = dp[row][0];  
        for (int col = 1; col < dp[row].length; col++) {  
            sum += dp[row][col];  
            dp[row][col] = sum;  
        }  
    }  
}

위 아래 방향으로 합산을 진행

public void colDirSum() {  
    for (int col = 0; col < dp[0].length; col++) {  
        int sum = dp[0][col];  
        for (int row = 1; row < dp.length; row++) {  
            sum += dp[row][col];  
            dp[row][col] = sum;  
        }  
    }  
}

이후 생성된 누적합 배열을 원본배열하고 합산하면 된다.

참고 블로그

블로그 링크