누적합이란?

누적합(cumulative sum)은 배열의 각 원소까지의 합을 미리 계산하여 누적한 값을 저장한 배열입니다. 이를 이용하면, 구간 합을 빠르게 계산할 수 있습니다. 구간 합은 배열에서 주어진 구간에 속한 모든 원소의 합을 의미합니다.

 

예를 들어, 배열 arr에서 2번째 원소부터 5번째 원소까지의 합을 계산해야 한다면, 다음과 같이 코드를 작성할 수 있습니다.

arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
start = 2
end = 5
sum = 0

for i in range(start, end+1):
    sum += arr[i]

print(sum)

위 코드는 구간 합을 계산하는 가장 간단한 방법입니다. 하지만, 배열의 크기가 크고 구간 합을 계산해야 하는 횟수가 많아질 경우에는 이 방법이 효율적이지 않습니다. 이를 해결하기 위해 누적합을 이용하면 효율적으로 구간 합을 계산할 수 있습니다.

 

누적합 배열을 만드는 방법은 매우 간단합니다. 배열 arr의 첫 번째 원소부터 각 원소까지의 합을 누적하여 저장한 배열을 만들어 놓으면 됩니다. 이를 수식으로 나타내면 다음과 같습니다.

cumulative_sum[i] = cumulative_sum[i-1] + arr[i]

이를 이용하여 구간 합을 계산하려면, 구간의 시작점과 끝점을 알고 있어야 합니다. 예를 들어, 배열 arr에서 2번째 원소부터 5번째 원소까지의 합을 구하려면, 누적합 배열 cumulative_sum에서 2번째 원소부터 5번째 원소까지의 합을 계산하면 됩니다.

cumulative_sum = [1, 3, 6, 10, 15, 21, 28, 36, 45, 55]
start = 2
end = 5

if start == 0:
    print(cumulative_sum[end])
else:
    print(cumulative_sum[end] - cumulative_sum[start - 1])

이 코드는 구간 합을 구하는 방법 중 하나입니다. 시작점이 0인 경우와 아닌 경우를 따로 처리해주어야 합니다.

 

시간 복잡도는 배열의 크기가 N일 때, 누적합 배열을 만드는데 O(N)의 시간이 걸립니다. 구간 합을 계산하는 데는 O(1)의 시간이 걸리므로, 전체적으로 배열을 선형적으로 한 번만 탐색하면 구간 합을 구할 수 있기 때문에, 구간 합을 여러 번 구해야 하는 경우에는 누적합을 이용하는 것이 효율적입니다.

 

또한, 누적합을 이용하면 배열의 일부를 업데이트하고자 할 때도 효율적입니다. 배열의 특정 원소를 업데이트하면, 그 원소 이후의 모든 누적합이 변경됩니다. 이를 다시 계산하는 것은 비효율적이므로, 업데이트된 원소부터 끝까지의 누적합만 다시 계산하면 됩니다.

누적합을 이용하면 구간 합을 빠르게 계산할 수 있지만, 누적합 배열을 만드는 데 O(N)의 시간이 걸리기 때문에, 배열의 크기가 작을 경우에는 구간 합을 계산하는 것보다 오히려 느릴 수 있습니다. 따라서, 배열의 크기와 구간 합을 계산하는 횟수에 따라서 적절한 방법을 선택해야 합니다.

 

누적합을 이용하는 방법은 다양한 문제에서 활용됩니다. 예를 들어, 수열에서 가장 긴 증가하는 부분 수열의 길이를 구하는 문제에서도 누적합을 이용할 수 있습니다. 이 문제는 다이나믹 프로그래밍 알고리즘을 이용하여 O(N^2)의 시간이 걸리지만, 누적합을 이용하면 O(NlogN)의 시간 안에 해결할 수 있습니다.

 

따라서, 누적합은 구간 합을 빠르게 계산하는 데 활용되는 중요한 개념 중 하나이며, 여러 가지 문제에서 유용하게 활용될 수 있습니다.