Algorithm

[알고리즘] 구간 합, 누적 합(Prefix Sum)

목차 누적 합이란? 언제 사용할까? 예시 및 코드 누적 합이란? 누적 합이란 수열 An에 대해서 각 인덱스까지의 구간의 합을 구하는 것을 누적 합이라고 합니다. 예를 들어 [1, 2, 3, 4, 5] 라는 배열이 있을 때, 각 구간까지의 합을 구하는 배열인 [ 1, 3, 6, 10, 15] 을 구한다고 가정해보면 아래와 같이 2가지로 구할 수 있습니다. [ 첫번째 방법 ] 1 1+2 1+2+3 1+2+3+4 1+2+3+4+5 매번 현재 인덱스까지의 값을 반복하며 더해주기 [ 두번째 방법 ] 1 1+2 3+3 6+4 10+5 이전 인덱스까지의 누적합에 현재 값을 더해주기 어떤게 더 효율적일까요? 배열의 갯수인 n을 늘려 [1, 2, ..., 99999, 10000]로 비교해보겠습니다. [ 첫번째 방법 ] ..