Python으로 1차원 배열의 누적 합(Running Sum) 구하기

배열 nums가 주어졌을 때, 누적 합(running sum) 배열 rs의 i번째 값 rs[i]는 nums[0]부터 nums[i]까지의 모든 원소를 더한 값입니다. 즉, 앞에서부터 차례대로 값을 누적해 나간 결과 배열을 반환하는 것이 목표입니다.

누적 합의 개념

예를 들어 입력이 nums = [8,3,6,2,1,4,5]라면, 출력은 [8, 11, 17, 19, 20, 24, 29]가 됩니다. 그 이유는 다음과 같습니다.

rs[0] = nums[0] = 8
rs[1] = nums[0..1]의 합 = 8 + 3 = 11
rs[2] = nums[0..2]의 합 = 8 + 3 + 6 = 17
rs[3] = nums[0..3]의 합 = 8 + 3 + 6 + 2 = 19
... 이런 식으로 마지막 원소까지 반복됩니다

해결 접근 방법

이 문제는 다음 단계를 따라 해결할 수 있습니다.

• n := nums의 크기
• rs := [nums[0]] — 첫 번째 원소로 초기화
• i를 1부터 n-1까지 반복:
  • nums[i] := nums[i] + nums[i-1] — 이전 누적 값을 현재 값에 더함
  • rs의 끝에 nums[i]를 추가
• rs 반환

핵심 아이디어는 매번 처음부터 다시 합을 구하는 대신, 바로 앞의 누적 값을 재활용한다는 점입니다. 덕분에 시간 복잡도는 O(n), 공간 복잡도 역시 O(n)으로 효율적으로 처리됩니다.

Python 예제 코드

아래 구현을 통해 동작 방식을 더 잘 이해할 수 있습니다.

def solve(nums):
    n = len(nums)
    rs = [nums[0]]

    for i in range(1, n):
        nums[i] += nums[i-1]
        rs.append(nums[i])
    return rs

nums = [8,3,6,2,1,4,5]
print(solve(nums))

입력

[8,3,6,2,1,4,5]

출력

[8, 11, 17, 19, 20, 24, 29]

대안: itertools.accumulate 활용하기

파이썬에서는 표준 라이브러리인 itertools의 accumulate 함수를 사용하면 반복문 없이 한 줄로 누적 합을 구할 수 있습니다.

from itertools import accumulate

nums = [8,3,6,2,1,4,5]
print(list(accumulate(nums)))  # [8, 11, 17, 19, 20, 24, 29]

accumulate는 기본적으로 각 위치까지의 합을 순서대로 생성하므로, 직접 구현한 알고리즘과 동일한 결과를 훨씬 간결한 코드로 얻을 수 있습니다. 실무에서는 가독성과 유지보수 측면에서 이 방식을 권장합니다.