prefixsum

[알고리즘] 누적합, Prefix Sum (feat. Python, Javascript)

들어가며 누적합 알고리즘(Cumulative sum algorithm)은 주어진 배열에서 인덱스 범위 내의 원소들의 합을 빠르게 계산하는 알고리즘입니다. 이 알고리즘은 배열의 누적합 배열을 이용하여 간단하게 구현할 수 있습니다. 누적합 배열은 인덱스 i까지의 합을 저장한 배열로, 배열의 첫 번째 원소는 항상 0으로 초기화합니다. 누적합, 파이썬 def cumulative_sum(arr): cumsum = [0] * (len(arr) + 1) # 누적합 배열 초기화 for i in range(len(arr)): cumsum[i+1] = cumsum[i] + arr[i] # 누적합 계산 return cumsum 위 코드는 누적합 알고리즘을 구현한 Python 함수입니다. 함수는 배열을 인자로 받고, 배열의 ..