Terrible Developer's Guide to Coding

누적합 계산

Kim Minseo's photo
Kim Minseo

코딩 테스트에서는 N×M 크기의 배열에서 특정 범위를 처리하는 문제가 자주 등장한다. 일반 for문으로 처리하면 정답은 맞았을 수 있으나 효율성 테스트에서 시간 초과가 발생하는 것을 확인할 수 있을 것이다.

일반 for문 사용 시 단점

  • 시간 복잡도가 O(n^2)까지 증가할 수 있다.

  • 중복 계산 발생

    • 이전 값을 활용하지 못하고 처음부터 다시 계산

이를 해결할 수 있는 방법 중 하나로 누적합(Cumulative Sum)이 있다. 배열의 각 위치까지의 합을 계산하여 새로운 배열을 생성하는 방법이다.

1차원 배열

계산 방법

  • 기존 배열 A = [1, 2, 3, 4, 5]

  • 누적합 배열 S = [1, 1 + 2, 1 + 2 + 3, 1 + 2 + 3 + 4, 1 + 2 + 3 + 4 + 5] = [1, 3, 6, 10, 15]

    • 1 ~ 3번째까지의 합 = S[3] - S[0] = 10 - 1 = 9 = 2 + 3 + 4

위 계산 방법에서 알 수 있듯이 일반 for문은 1부터 3 위치까지의 합을 구하려면 아래와 같이 작성했을 것이다.

int A[5] = {1, 2, 3, 4, 5};
int sum = 0;
for (int i = 1; i <= 3; i++) {
  sum += A[i];
}

합을 구하기 위해 반복을 총 3번하게 되는데 배열의 크기가 작다면 문제 없지만, 만약 크기가 1000인 배열에서 300 ~ 999까지의 합을 구한다면 총 699번 반복하기 때문에 효율이 굉장히 떨어질 것이다.

누적합을 사용하게 되면 처음 누적합 배열을 만드는 반복문을 제외하면 반복 없이 부분합을 구할 수 있다. 마지막 위치의 값에서 [시작 위치 - 1] 값을 빼주면 된다.

int A[5] = {1, 2, 3, 4, 5};
int S[5];
S[0] = A[0];
for (int i = 1; i < 5; i++) {
  S[1] = S[i - 1] + A[i];
}

만약 특정 영역에만 값을 더해주고 싶을 때는 어떻게 하면 좋을까? 방법은 이러하다. 크기가 5인 A라는 배열에 1 ~ 3 위치에만 +3 해보자.

  • 기존 배열과 같은 크기의 값이 모두 0인 새 배열 B를 만든다.

  • B 배열에서 시작 인덱스에 해당하는 값에 +3을 해주고 (끝 인덱스 + 1)에 해당하는 값에 -3을 해준다.

    • A = {1, 2, 3, 4, 5}

    • B = {0, 3, 0, 0, -3}

  • B를 누적합으로 계산하면 더하고자 하는 인덱스에만 +3이 됨을 확인할 수 있다.

    • B = {0, 3, 3 + 0, 3 + 0, 0 + (-3)}

  • 이제 A와 B를 더해보면 원하는 결과가 나올 것이다.

    • A + B = {1 + 0, 2 + 3, 3 + 3, 3 + 4, 5 + 0} = {1, 5, 6, 7, 5}

2차원 배열

위 그림에서 파란 색으로 칠해진 부분의 합을 구하고 싶다. 녹색으로 칠한 열의 합과 적색으로 칠해진 값들의 합을 더하고 녹색과 적색이 겹치는 그림에서는 (0, 0)의 값만 제거한 값을 (0, 0)부터 (3, 3)까지의 합에서 빼면 쉽게 구할 수 있다. 그래서 각 위치에 누적합을 구하는 공식이 아래와 같다.

$$prefix[i][j]=arr[i][j]+prefix[i−1][j]+prefix[i][j−1]−prefix[i−1][j−1]$$

현재 위치의 값과 왼쪽 값, 위쪽 값을 더해주고 북서쪽 방향으로 대각선에 있는 값을 제거해주면 된다.

부분합 계산 방법

N × M 크기의 2차원 배열에서 (a, a)부터 (b, b)까지의 합을 구하고 싶다고 해보자

  • (N + 1) x (M + 1) 크기의 값이 모두 0인 2차원 배열을 만든다.

  • (1, 1)부터 위 공식처럼 누적합을 계산해 배열에 넣어준다.

  • (b, b)에 위치한 값에서 (a - 1, b), (b, a - 1) 값을 빼준다.

    • $$prefix[b][b] - prefix[b][a - 1] - prefix[a - 1][b]$$

  • (a - 1, b)와 (b, a - 1)이 서로 겹치는 값이 두 번 계산되었을 것이기 때문에 겹치는 위치의 값을 더해준다.

    • $$prefix[b][b] - prefix[b][a - 1] - prefix[a - 1][b] + prefix[a - 1][a - 1]$$

  • 계산 결과가 부분합 값이다.

algorithms