[5, 7, 8, 2, 4, 0, -1, 2, 7, 3]
위의 배열에 다음의 연산을 차례로 진행해 보자.
- 0~5번째 원소에 2를 더한다.
- 3~7번째 원소에 5를 더한다.
- 2~6번째 원소에 4를 뺀다.
- 5~9번째 원소에 3을 더한다.
위의 연산 결과를 얻기 위해서는 총 몇번의 연산이 필요할까?
각 단계에 연산을 적용해야 하는 원소의 개수는 6, 5, 5, 5 개 이므로 21번의 연산이 필요하다.
그런데, 이를 더 줄일 순 없을까?
위의 각 단계마다 각 특정 구간에 가해지는 연산은 동일하다.
이 경우, 우리는 누적합 배열을 사용해 연산을 줄일 수 있다.
누적 합
누적합 배열은 다음과 같은 방법으로 구할 수 있다.
- 가장 첫번째 원소는 기존의 원소를 그대로 사용한다.
- i번째 원소는 누적합 배열의 i-1번째 원소 + 기존 배열의 i번쨰 원소 의 결과값을 사용한다.
즉, 배열을 앞에서부터 누적하여 더한 값을 각 자리에 저장하는 배열이 누적합 배열이다.
위에서 사용했던 [5, 7, 8, 2, 4, 0, -1, 2, 7, 3] 배열의 누적합 배열은 다음과 같다.
[5, 12, 20, 22, 26, 26, 25, 27, 34, 37]
이 배열의 가장 큰 특징은 누적하여 더한다는 것인데, 이 특징 덕분에 우리는 다음의 특성을 얻을 수 있다.
n번째 원소에 k의 값이 더해진다면, 이후에 계산되는 n+1 이상의 모든 누적합에는 k가 누적된다.
즉, 4번째 원소인 4의 값을 4에 2가 더해진 6으로 교체한다면, 누적합 배열에서의 4번째 이후의 원소들은 모두 기존의 누적합 배열보다 2 큰 수를 갖게 된다.
누적 합 배열의 활용
이 누적 합 배열의 특성을 이용하면 특정 구간에 가해지는 공통된 연산들을 빠르게 처리할 수 있다.
다시 한번 위에서 주어진 연산을 살펴보자.
- 0~5번째 원소에 2를 더한다.
- 3~7번째 원소에 5를 더한다.
- 2~6번째 원소에 4를 뺀다.
- 5~9번째 원소에 3을 더한다.
이 때, 각 자리에 가해지는 연산을 새로운 배열로 저장해 보자.
즉, 4번째 원소에 3이 더해진다면 연산 배열의 4번째 자리에 3을 저장하는 식으로 말이다.
아무런 연산이 가해지지 않은 상태를 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]으로 저장해 두자.
이제, 각 연산을 수행한 이후의 연산 배열을 계산해 보자.
1번 연산이 수행된 시점에서 0~5번째 원소에 5가 더해지므로 연산 배열은 [2, 2, 2, 2, 2, 2, 0, 0, 0, 0] 가 된다.
이후의 연산들에 대해서는 연산 배열의 변화 형태만 나열하겠다.
- [2, 2, 2, 7, 7, 7, 5, 5, 0, 0] →
- [2, 2, -2, 3, 3, 3, 1, 5, 0, 0] →
- [2, 2, -2, 3, 3, 6, 4, 8, 3, 3]
마지막으로 연산 배열의 각 값을 기존 배열 [5, 7, 8, 2, 4, 0, -1, 2, 7, 3] 에 더해 연산을 모두 수행하면 다음의 결과 배열을 얻을 수 있다.
[7, 9, 6, 5, 7, 6, 3, 10, 10, 6]
이 방법은 기존의 방법에 비해 좋아보이지는 않는다. 여전히 연산 배열을 구하기 위해 총 21번의 연산이 수행되었으며, 이후 기존의 배열에 연산을 수행하기 위해 10번의 연산이 추가로 진행되었다.
이제, 누적합을 활용해 보자.
누적합은 위의 연산 배열을 구하는 데 사용된다.
이 때, 다음의 특징을 잘 기억하자.
누적합에서 n번째에 k의 값이 더해진다면, n번째 이후의 모든 누적합에는 k만큼 증가한다.
즉, [0, 0, 0, 0, 0, 0, 0, 0, 0, 0] 배열의 0번째에 2를 더한 [2, 0, 0, 0, 0, 0, 0, 0, 0, 0] 배열의 누적합은 [2, 2, 2, 2, 2, 2, 2, 2, 2, 2]가 된다.
이를 다음처럼 활용할 수도 있다. 전체 배열의 n_s번째에 k를 더하고, n_e + 1번째 원소에 k를 뺀다면 전체 배열의 n_s부터 n_e까지의 누적합에만 k가 증가한다.
무슨 말이냐면,,,
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0] 배열의 0번째에 2를 더하고, 6번째에 2를 뺀 [2, 0, 0, 0, 0, 0, -2, 0, 0, 0] 배열의 누적합은 [2, 2, 2, 2, 2, 2, 0, 0, 0, 0]가 된다는 것이다!
이 누적합 어디서 많이 본 배열 아닌가? 이 배열은 첫번째 연산만 수행한 이후의 누적합과 같다!
이 누적합의 진가는, 여러개의 연산을 순차적으로 진행할 때 나타난다.
위의 특징을 활용하기 위해 각 연산에 대해 n_s번째 원소에 k를 더하고, n_e + 1번째 원소에 k를 빼는 연산만 수행해 준 이후 마지막에 한번만 누적합을 계산하면 전체 연산에 대한 연산 배열을 쉽게 구할 수 있다.
즉, 다음의 연산에 대해
- 0~5번째 원소에 2를 더한다.
- 3~7번째 원소에 5를 더한다.
- 2~6번째 원소에 4를 뺀다.
- 5~9번째 원소에 3을 더한다.
연산 배열은 다음과 같이 변화시킨 다음
- [0, 0, 0, 0, 0, 0, 0, 0, 0, 0] → (1번연산)
- [2, 0, 0, 0, 0, 0, -2, 0, 0, 0] → (2번 연산)
- [2, 0, 0, 5, 0, 0, -2, 0, -5, 0] → (3번 연산)
- [2, 0, -4, 5, 0, 0, -2, 4, -5, 0] → (4번 연산)
- [2, 0, -4, 5, 0, 3, -2, 4, -5, 0]
연산 배열에 대해 누적 합을 계산하면 다음의 [2, 2, -2, 3, 3, 6, 4, 8, 3, 3]의 전체 연산 배열을 구할 수 있다는 것이다!
이처럼 각 구간에 대한 연산을 기억해 두는 O(1)의 연산들을 수행한 이후, 마지막에 O(n)의 연산을 한번만 진행해 주면 훨씬 빠르게 특정 구간에 대한 연산 결과를 구할 수 있는 것이다!!
아래는, 1차원이 아닌 2차원 배열에서 구간 합 배열을 이용해 볼 수 있는 문제이다.
[파괴되지 않은 건물](https://school.programmers.co.kr/learn/courses/30/lessons/92344)
해당 문제의 풀이는 벨로그에 정리해 두었다.
댓글