배열의 구간 변화 빠르게 구하기

알고리즘 문제를 해결하는 도중에 해결하기 어려운 부분이 있었습니다.

하나의 1차원 배열을 예로 들어보겠습니다.

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

위처럼 1차원 배열이 존재합니다. 이 때, 구간별 변경값이 주어집니다.

배열의 인덱스 2부터 7까지 3을 더한다.

이 때 어떻게 계산해야할까요?

for문을 통한 계산

가장 먼저 드는 생각은 for문을 통해 2부터 7까지 각각 3을 더해주는 방법입니다. 배열의 길이가 N이고 변경값이 M회 주어진다면, 시간복잡도는 $O(N * M)$입니다.

이를 더 빠르게 계산하는 방법은 없을까요?

이런 경우, 누적합 을 이용할 수 있습니다.

누적합을 이용한 구간 변화

예시를 통해 설명해보겠습니다.

array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

위 배열에 구간 변화가 생긴다면, 이 배열보다 길이가 1이 더 긴 배열을 생성합니다.

temp = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

이후 2부터 7까지 3만큼 증가시키고 싶다면, temp[2]에 3을 증가시키고 temp[8]에 3을 감소시킵니다. 즉, 시작 지점은 해당 값을 더하고, 종료 지점보다 한 칸 뒤에는 해당 값을 감소시킵니다.

temp = [0, 0, 3, 0, 0, 0, 0, 0, -3, 0, 0]

그 후 temp를 첫번째 인덱스부터 누적합을 구하게 되면 어떻게 될까요?

temp = [0, 0, 3, 3, 3, 3, 3, 3, 0, 0, 0]

2부터 7까지 3을 더한 결과와 같습니다. 이 때, 결국 더하는 과정에서 2부터 7까지 반복해야 하기 때문에 같은 시간복잡도가 소요되는게 아닐까 싶을 수 있지만, 이는 여러 변화를 반영하게 될 때 훨씬 유용하게 사용될 수 있습니다.

만약, 구간 변화가 2번 이루어진다면 어떻게 계산하게 될까요?

2부터 7까지 3을 증가시키고, 5부터 8까지 1을 감소시켜야 한다고 가정해보겠습니다. 그렇다면 다음과 같이 temp 배열에 연산을 수행하게 됩니다.

temp = [0, 0, 3, 0, 0, 0, 0, 0, -3, 0, 0] // 2부터 7까지 증가

temp = [0, 0, 3, 0, 0, -1, 0, 0, -3, 1, 0] // 5부터 8까지 감소

temp = [0, 0, 3, 3, 3, 2, 2, 2, -1, 0, 0] // 누적합

각 연산은 O(1)에 수행됩니다. 이전에는 구간 길이만큼 반복하던 과정에서 상당히 시간을 줄일 수 있습니다.

이후 array에 temp를 더합니다.

array = [1, 2, 6, 7, 8, 8, 9, 10, 8, 10]

이처럼 누적합을 이용하면 O(N * M)에서 O(N + M)으로 비교적 빠르게 수행할 수 있습니다.