왜 써야하는가?
배열의 부분합을 구할 때에 브루트포스(완전탐색)로 구하게 된다면 시간 복잡도가 O(n)이 걸린다. 하지만 누적합을 이용한다면 O(1)의 시간이 걸리게 된다.
더 자세하게 설명하자면 구간의 길이가 M이고 N개의 구간의 갯수를 가지고 있다면 시간 복잡도는 O(NM)이 된다. 최악의 경우 O(N^2)이 되버릴 것이다.(처음부터 끝까지 누적합을 구하게 되는 경우)하지만 누적 합 방식을 이용한다면 시간 복잡도를 O(N + M)까지 줄일 수 있다. 전처리 과정인 모든 배열의 누적합을 구하는데 O(N)의 복잡도를 갖고 연산 자체는 O(1)의 시간을 갖기 때문이다.
문제.
1차원 누적합
백준 - 구간 합 구하기4
배열 에서 여러개의 구간들의 합을 구하라고 할 때 누적합을 이용해서 푸는 문제입니다.
예를 들어 [5, 4, 3, 2, 1] 배열이 있을 때 1, 3번째 원소의 합, 2번쨰 4번째 원소의 합을 구해야 할때 누적합을 이용한다면 쉽게 구할 수 있습니다.
기존 배열 + 1 만큼의 길이를 가진 새로운 배열을 만들어줍니다.
[0, 0, 0, 0, 0, 0] 이 배열을 sum이라는 배열이라고 가정하겠습니다.
[5, 4, 3, 2, 1] 이 배열은 arr이라고 가정하겠습니다.
sum[i] = sum[i - 1] + arr[i]
위의 점화식의 전처리 과정을 거친다면 sum 배열은
[0, 5, 9, 12, 14, 15]의 배열이 됩니다.
b-a 구간의 누적합을 구하기 위해서는 b구간에서 a - 1의 구간까지를 빼주시면 됩니다.
arr 1 - 3의 구간의 합은 sum[3] - sum[0] 즉 , 12가 됩니다.
2차원 누적합
프로그래머스 - 파괴되지 않은 건물
1차원 누적합의 경우
1 2 4 8 9
0, 3까지 -2만큼의 변화를 준다고 가정했을 때
-1 0 2 6 9
의 결과값이 나와야합니다.
위의 예시의 경우
-2 0 0 0 2
새로운 배열을 만들어 줍니다.
왼쪽에서 오른쪽으로 누적합을 구해줍니다.
-2 -2 -2 -2 0
기존의 배열인 [1,2,4,8,9]와 합을 구하게 되면 [-1 0 2 6 9]가 나오게 됩니다. 즉, 1차원 배열의 a번째 원소부터 b번째 원소까지 c만큼의 변화를 주겠다고 하면 새로운 배열의 a번째 원소에 c를 더하고 b+1번째 원소에 c를 빼면 됩니다
하지만 2차원 누적합의 경우에는
0 0 0
0 0 0
0 0 0
배열이 있을 때 0, 0에서 2, 2까지 n만큼의 변화를 준다면 1차원 누적합의 아이디어를 떠올리면서 각 행에 적용시키면, 1차원 배열의 0번째 원소부터 2번째 원소 까지 n만큼의 변화를 3개의 행에 적용시키는 것이 된다.
n 0 0 -n
n 0 0 -n
n 0 0 -n
위 행렬을 다시 열만 따로 보면, 가장 왼쪽 열의 0번째 원소부터 2번째 원소까지 n만큼의 변화와 가장 오른쪽 열의 0번째 원소부터 2번째 원소까지 -n만큼의 변화와 같습니다. 각 열에 위의 아이디어를 적용시키면 아래와 같아집니다.
n 0 0 -n
0 0 0 0
0 0 0 0
-n 0 0 n
즉, 2차원 배열에서 (x1, y1)부터 (x2, y2)까지 n만큼의 변화는 (x1, y1)에 +n, (x1, y2 + 1)에 -n, (x2 + 1, y1)에 -n, (x2 + 1, y2 + 1)에 +n을 한 것과 같다. 위의 배열을 위에서 아래로 누적합한 뒤, 왼쪽에서 오른쪽으로 누적합 하거나, 왼쪽에서 오른쪽으로 누적합 한 뒤 위에서 아래로 누적합하면 처음에 의도한 (0,0)부터 (2,2)까지 n만큼 변화시키는 배열이 나오는 것을 확인할 수 있다.
n n n 0
n n n 0
n n n 0
0 0 0 0
이러한 방법으로 처리 시간을 O(1)만에 처리할 수 있게 된다. 따라서 이차원 누적합의 시간복잡도는 O(K + N * M)이 된다.
