[알고리즘] 누적합, 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 함수입니다. 함수는 배열을 인자로 받고, 배열의 누적합 배열을 반환합니다. 함수 내부에서는 누적합 배열을 초기화하고, 각 인덱스까지의 누적합을 계산하여 누적합 배열에 저장합니다.

 

 

 

 

 

 

---

 

 

 

 

 

 

누적합, 자바스크립트

function cumulativeSum(arr) {
    let cumsum = new Array(arr.length + 1).fill(0); // 누적합 배열 초기화
    for (let i = 0; i < arr.length; i++) {
        cumsum[i+1] = cumsum[i] + arr[i]; // 누적합 계산
    }
    return cumsum;
}

 

위 코드는 누적합 알고리즘을 구현한 JavaScript 함수입니다. 함수는 배열을 인자로 받고, 배열의 누적합 배열을 반환합니다. 함수 내부에서는 누적합 배열을 초기화하고, 각 인덱스까지의 누적합을 계산하여 누적합 배열에 저장합니다.

 

 

 

 

 

 

---

 

 

 

 

 

 

마치며

누적합 알고리즘은 배열에서 인덱스 범위 내의 원소들의 합을 빠르게 계산할 수 있는 간단하고 유용한 알고리즘입니다. 위의 예시 코드를 참고하여 Python과 JavaScript에서 누적합 알고리즘을 구현해보세요!