구간 합 구간 합 빠르게 계산하기 문제 해결 아이디어 동일한 반복된 계산을 수행하지 않고 DP처럼 메모이제이션 기법을 이용하는 것 * 소스 코드 # 데이터의 개수 N과 전체 데이터 선언 n = 5 data = [10, 20, 30, 40, 50] # 접두사 합(Prefix Sum) 배열 계산 sum_value = 0 prefix_sum = [0] for i in data: sum_value += i prefix_sum.append(sum_value) # 구간 합 계산 (세 번째 수부터 네 번째 수까지) left = 3 right = 4 print(prefix_sum[right] - prefix_sum[left - 1])
