재취업 준비/코테
누적합이란?
누적합(cumulative sum)은 배열의 각 원소까지의 합을 미리 계산하여 누적한 값을 저장한 배열입니다. 이를 이용하면, 구간 합을 빠르게 계산할 수 있습니다. 구간 합은 배열에서 주어진 구간에 속한 모든 원소의 합을 의미합니다. 예를 들어, 배열 arr에서 2번째 원소부터 5번째 원소까지의 합을 계산해야 한다면, 다음과 같이 코드를 작성할 수 있습니다. arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] start = 2 end = 5 sum = 0 for i in range(start, end+1): sum += arr[i] print(sum) 위 코드는 구간 합을 계산하는 가장 간단한 방법입니다. 하지만, 배열의 크기가 크고 구간 합을 계산해야 하는 횟수가 많아질 경우에는 이 ..
