누적 합 배열 만들기

하나의 배열에 대해 수백 개의 구간 합 질의에 답한다고 생각해 보십시오. 각 구간을 처음부터 매번 더하면 느립니다. 누적 합으로 이 문제를 해결할 수 있습니다. 🚀

누적 합 배열은 각 인덱스에 그 위치까지의 모든 원소 합을 저장합니다. 미리 한 번 계산해 두면 느린 합 계산을 즉시 답할 수 있습니다.

[3, 1, 4]의 경우 누적 합은 3, 4, 8이 됩니다. 이렇게 점점 커지는 합계 리스트가 바로 누적 합입니다.

각 항목은 이전 합계에 현재 원소를 더한 값입니다. 이 한 줄짜리 점화식이 전체 기법의 핵심입니다.

배열을 한 번 훑으며 누적 합계를 유지하십시오. 각 단계에서 새로운 합을 추가하므로 배열을 만드는 과정은 한 번의 선형 순회입니다.

누적 합을 앞의 0에서 시작하면 prefix[i]가 처음 i개 원소의 합을 담게 됩니다. 덕분에 나중에 구간 합을 깔끔하게 계산할 수 있습니다.

앞에 0을 두면 prefix[k]는 a[0] + ... + a[k-1]과 같습니다. 이 규칙을 정확히 지키면 까다로운 인덱스 하나 차이 오류를 예방할 수 있습니다.

누적 합 배열을 만들 때 각 원소를 정확히 한 번씩 확인하므로 O(n) 시간이 걸립니다. 이 비용은 한 번만 지불하고 이후에는 계속 재사용합니다.

핵심 이점은 절충입니다. 먼저 선형 순회를 한 번 수행하면 이후의 모든 합 질의가 반복문 대신 빠른 조회가 됩니다.

표준 라이브러리가 합계를 대신 계산해 줄 수 있습니다. itertools.accumulate는 한 번의 깔끔한 호출로 누적 합을 만듭니다.

누적 합 배열은 입력과 길이가 같고 원소 하나가 더 있습니다. 입력이 매우 크다면 메모리 사용량이 두 배가 된다는 점을 기억하십시오.

누적 합 배열을 만들었습니다. 인덱스 0에는 보통 무엇이 들어갈까요?

앞에 0을 두어 인덱스를 깔끔하게 만든 뒤, O(n) 한 번의 순회로 누적 합 배열을 만드는 방법을 배웠습니다. 한 번 미리 계산하고 다시 사용하십시오. ✅