Cumulative Sum Algorithm (누적 합)

# 정의

 

누적합 알고리즘(Cumulative Sum Algorithm)은, 1차원 배열의 일부 또는 전체 원소들의 합을 빠르게 구할 수 있는 알고리즘입니다. 이 알고리즘은 입력 배열의 각 원소를 한 번씩만 방문하면서, 각 위치에서 누적합을 계산하고, 미리 계산해 둔 누적합을 사용하여 구간 합을 계산합니다.

글로만 읽어도 이해가 갈 정도로 굉장히 간단한 알고리즘입니다. 그래서 겉보기에 그냥 당연한 얘기처럼 보입니다. 하지만 오늘 알고리즘 문제를 풀면서 엄청난 활용을 발견했습니다. 

 

---

# Code

 

가장 기본적인 파이썬 코드입니다. 정말 간단합니다.

# 입력 배열을 정의합니다.
arr = [1, 2, 3, 4, 5]

# 누적합 배열을 초기화합니다.
prefix_sum = [0] * len(arr)
prefix_sum[0] = arr[0]

# 누적합 배열을 계산합니다.
for i in range(1, len(arr)):
    prefix_sum[i] = prefix_sum[i-1] + arr[i]

# 구간 합을 계산합니다.
sum_ = prefix_sum[3] - prefix_sum[1-1]

print(sum_)  # 출력: 7

 

---

# 활용

 

[0, 0, 0, 0, 0, 0, 0, 0]

다음과 같이 길이가 8인 0으로 채워진 배열이 있다. 이 배열에 0~2 인덱스까지 10을 더하고 싶어합니다.

이때 시작 인덱스에 +10, 마지막 인덱스+1 에 -10 을 합니다.

 

[10, 0, 0, -10, 0, 0, 0, 0]

그 다음 0~8까지 누적합을 구합니다.

[10, 10, 10, 0, 0, 0, 0, 0]

의도했던대로 0~2 인덱스까지 10을 더할 수 있습니다.

 

이것만 보면 0~2인덱스에 10을 일일이 더해주는것과 수행시간이 차이가 안납니다. 하지만 여러 구간에서 이 과정들이 일어난다면 어떨까요?

 

 

[10, 20, 30, -10, -20, -30, 0, 0]

[0~2] 에 +10 / [1~3]에 +20 / [2~4]에 +30 을 해보고 싶다고 하고 아까 방식으로 초기값을 만들어줍시다.

[10, 30, 60, 50, 30, 0, 0, 0]

그런 다음 누적합을 구하면 덧셈처리를 한꺼번에 처리할 수 있습니다.

 

이런 활용이 다차원배열에서도 적용되므로 수행시간에 엄청난 절약을 가져옵니다. 좀 더 자세한 설명을 원하면 블로그 글을 읽어보길 바랍니다. 

https://kimjingo.tistory.com/155

[Programmers] 파괴되지 않은 건물 (Python 풀이) - 2022 KAKAO BLIND RECRUITMENT

 

---

# 수행시간

이 알고리즘의 시간복잡도는 O(n)입니다. 이는 입력된 배열의 크기에 비례하는 선형 시간 복잡도를 가지는 것을 의미합니다. 알고리즘은 배열을 한 번 순회하며, 각 인덱스마다 현재까지의 누적합을 계산하여 누적합 배열에 저장합니다. 따라서 배열의 크기가 n일 때, 시간복잡도는 n번의 연산을 수행하므로 O(n)이 됩니다.

 

 

 

---

# Reference

ChatGPT

https://kimjingo.tistory.com/155