누적합 알고리즘(prefix sum)

이 알고리즘은 "값의 변경이 없을때" 빠르게 구간합을 구하기 위한 알고리즘으로 시간 복잡도는 O(N) 입니다.일단 배열 a를 받아 줍니다. 예시)a = [0] + list(map(int,input().split())) #zero index사용 x 그 후, 1부터 a의 길이 번 반복하여 전에있는 값을 더해 줍니다. 예시)a = [0] + list(map(int,input().split())) #zero index 사용 xfor i in range(1,len(a)): #index error을 방지 하기 위하여 1부터 시작 a[i] += a[i-1] # 자신에다가 뒤에 닜는 값을 더함 이때 a가 [1,2,3,4,5]라고 가정하면, 다음과 같이 변경 됩니다.[1,3,6,10,15] 이제 이걸로 구간합을 구하..

2024.10.24