구간 합
구간 합 빠르게 계산하기
문제 해결 아이디어
- 동일한 반복된 계산을 수행하지 않고 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])
반응형
'Algorithm > algorithm_study' 카테고리의 다른 글
개발형 코테 (0) | 2021.04.29 |
---|---|
Two Pointers (0) | 2021.04.29 |
기타 그래프 이론 (0) | 2021.04.19 |
최단 경로 알고리즘(Shortest Path) (0) | 2021.03.30 |
다이나믹 프로그래밍(Dynamic Programming) (0) | 2021.03.18 |