[Algorithm] 누적 합
[5, 7, 8, 2, 4, 0, -1, 2, 7, 3] 위의 배열에 다음의 연산을 차례로 진행해 보자. 0~5번째 원소에 2를 더한다. 3~7번째 원소에 5를 더한다. 2~6번째 원소에 4를 뺀다. 5~9번째 원소에 3을 더한다. 위의 연산 결과를 얻기 위해서는 총 몇번의 연산이 필요할까? 각 단계에 연산을 적용해야 하는 원소의 개수는 6, 5, 5, 5 개 이므로 21번의 연산이 필요하다. 그런데, 이를 더 줄일 순 없을까? 위의 각 단계마다 각 특정 구간에 가해지는 연산은 동일하다. 이 경우, 우리는 누적합 배열을 사용해 연산을 줄일 수 있다. 누적 합 누적합 배열은 다음과 같은 방법으로 구할 수 있다. 가장 첫번째 원소는 기존의 원소를 그대로 사용한다. i번째 원소는 누적합 배열의 i-1번째 원소..
2023. 5. 1.