[알고리즘] 누적합 알고리즘

누적합 알고리즘은 배열의 각 원소에 대한 누적된 합을 구하는 알고리즘입니다. 누적합 알고리즘을 사용하면 배열의 부분합을 낮은 시간복잡도로 효율적으로 구할 수 있고 구간 합을 여러번 계산할 때 주로 사용됩니다.

1차원 누적합

arr = [a1, a2, a3, a4] 을 누적합 배열로 계산하게 되면 다음과 같이 계산됩니다.
accumulated_sum = [a1, a1 + a2, a1 + a2 + a3, a1 + a2 + a3 + a4]
특정 배열 구간(i, j)의 합은 accumulated_sum[j] - accumulated_sum[i - 1]로 표현할 수 있습니다.

public int[] accumulate(int[] arr) {
  int n = arr.length;
  int[] accumulatedSum = new int[n];
  accumulatedSum[0] = arr[0];

  for (int i = 1; i < n; i++) {
      accumulatedSum[i] = accumulatedSum[i - 1] + arr[i];
  }

  return accumulatedSum;
}

2차원 누적합

2차원 배열 누적합은 각 원소는 해당 위치까지의 행과 열의 모든 원소의 합입니다.

arr = [
[a11, a12, a13],
[a21, a22, a23],
[a31, a32, a33]
]
위와 같은 배열의 누적합은 다음과 같습니다.

accumulated_sum = [
[a11, a11 + a12, a11 + a12 + a13],
[a11 + a21, a11+ a21 + a12 + a22, ...],
[a11 + a21 + a31, a11 + a21 + a12 + a22 + a32, ...]
]

accumulated_sum[i][j] = arr[i][j] + accumulated_sum[i−1][j] + accumulated_sum[i][j−1] − accumulated_sum[i−1][j−1]

public static int[][] accumulate(int[][] arr) {
  int m = arr.length;
  int n = arr[0].length;

  int[][] accumulatedSum = new int[m][n];
  accumulatedSum[0][0] = arr[0][0];

  // 첫 번째 행 초기화
  for (int j = 1; j < n; j++) {
      accumulatedSum[0][j] = accumulatedSum[0][j - 1] + arr[0][j];
  }

  // 첫 번째 열 초기화
  for (int i = 1; i < m; i++) {
      accumulatedSum[i][0] = accumulatedSum[i - 1][0] + arr[i][0];
  }

  // 나머지 부분 계산
  for (int i = 1; i < m; i++) {
      for (int j = 1; j < n; j++) {
          accumulatedSum[i][j] = arr[i][j] + accumulatedSum[i - 1][j] + accumulatedSum[i][j - 1] - accumulatedSum[i - 1][j - 1];
      }
  }

  return accumulatedSum;
}