누적합

누적합 알고리즘은 최근에 공부를 하며 접하게 되었다. 누적합의 개념 자체는 매우 간단하다. 특정한 배열이 있을 때, 해당 배열까지의 합을 나타내는 말이다. 즉 [1,2,3,4,5] 라는 배열이 있을 때 이 배열의 누적합을 배열로 나타내면 [1,3,6,10,15]가 되는 것이다.(물론 누적합 알고리즘의 구현에 편의를 위해 인덱스가 하나 큰 배열을 만들거나 하는 경우도 있다.)

누적합의 장점

누적합을 사용할 경우 time complexity의 관점에서 큰 이득을 가져다 준다. 이는 누적합의 경우 미리 계산!! 해둘 수 있기 때문이다. 만약 어떠한 배열에서 a번째 부터 b번째 까지의 수의 합을 알아야 한다고 가정해보자.

1. 누적합을 사용하지 않을 경우
   a 부터 b 까지 직접 값들을 더해나가야 하며, 이 경우 0<=a<=b<=n에서 최악의 경우 O(N)의 시간이 걸리게 된다. 여기에 이러한 a~b 까지의 합을 구해야 하는 경우가 m번 존재한다면 O(NM)의 시간이 걸리게 된다.

2. 누적합을 사용하는 경우
   누적합을 사용하려면 먼저 계산이 필요하다. 이 계산 자체가 전체를 탐색해야 하기 때문에 O(N)이 일단 필요하다. 하지만 그 이후 a~b까지의 합은 누적합 배열에서 (b까지의 합) - (a-1 까지의 합)으로 나타낼 수 있다. 즉 O(2) == O(1)로 해결할 수 있게 된다. 이 경우가 m번 존재한다 해도 결국 O(M) 만큼의 시간이 걸릴 것이고 결국 총 O(N+M)만큼 들게 된다.

따라서 M이 크면 클수록 누적합을 활용하는 것이 O(NM) >= O(N+M)이기에 시간 복잡도에서 큰 이점을 갖는다.

구현

사실 누적합은 구현이라고 할 것이 없다. 말 그대로 특정한 배열에 따라 해당 원소까지의 합을 미리 구해놓으면 되니 말이다. 다만 1차원이 아닌 2차원 배열로 확장할 경우 누적합을 잘 구할 수 있는 식 정도는 존재한다.

해당 내용은 추후에 복습을 하며 다시 추가해두겠다.

팁

이 누적합을 잘 활용할 수 있는 상황이 있다. 바로 연속되는 구간에 일정한 값을 더하거나 빼고 싶을 때이다. 만약 길이가 10인 배열의 3~7까지 1씩 더하고 싶다고 생각해보자. 이런 경우가 하나라면 그냥 하면 된다. 단순히 3~7까지 더하면 되는 것이다. 허나 이런 경우가 매우 많아 질 경우 문제가 된다. 이 때 사용할 수 있는 팁이다.

위 사진을 보며 설명해보자. 우선 3~7까지 1씩 더하고 싶은 거니까 목표는 (1)번과 같다.

1. 우선 (2)번과 같이 배열의 보다 크기가 1만큼 큰 배열을 만들자.
2. 수를 더하기 원하는 시작점(ex: 3)에 더하고 싶은 수(ex: 1)를, 수를 더하기 원하는 마지막점 + 1 자리에 (ex: 7 + 1 = 8)자리에 더하고 싶은 수에 -1을 곱해 (ex: -1) 배치하자. 이 경우 (3)번과 같은 형태가 될 것이다.
3. 그리고 (3)번 배열의 누적합 배열을 구해보자. 그러면 (4)번과 같은 형태가 되며 (1)번 배열의 맨 마지막에 0이 하나 붙어 있는 형태가 된다.
4. 이렇게 만든 (4)번 배열을 원래 기존의 배열에 각 원소끼리 덧셈을 하면 기존 배열에 3~7번 원소에 1을 더한 배열을 구할 수 있다.

이렇게 보면 아니 저게 무슨 의미가 있냐~ 이럴 수 있다. 하지만 위에서 언급했던 것 처럼, 해당 작업을 여러번 해야 될 경우 의미가 있다. 여러 구간에 여러 수를 더하고나 빼야 한다면 (2)번과 같은 배열을 만들어 (2) -> (3)으로 만드는 작업을 반복적으로 진행하자. 그렇게 되면 배열에 하고싶은 여러 작용을 (3) 배열 하나로 나타낼 수 있게 된다. 그 후 (3)의 누적합 배열을 구해 기존 배열과 계산만 해주면 훨씬 빠르게 간편하게 목표한 일을 달성할 수 있다.

연습 문제

아래 문제들을 누적합을 이용하면 효과적으로 해결할 수 있는 코딩테스트 문제들이다. 시간이 된다면 꼭 풀어보는 것을 추천한다.
파괴되지 않은 건물
광고 삽입 문제