Prefix sum
$N$개의 숫자가 늘어서 있다. L번째 숫자부터 R번째 숫자까지의 합을 구하라는 질문이 여러 개 들어올 때, 각각을 모두 빠르게 구할 수 있을까? 2018/07/27 - [알고리즘 문제풀기/# 자료구조] - 구간의 합 구하기prefix sum 기법을 사용하면 이 "구간의 합 구하기" 문제를 빠르게 풀 수 있다. 또한, 어떤 문제에서는 prefix sum을 구해보면 생각하지 못했던 성질이 나타나서, 그게 문제를 푸는 열쇠가 되기도 한다. 아예 prefix sum 값에 관한 문제가 나오기도 한다. prefix sum은 간단하지만 중요한 개념이다. 그래서 도대체 그 prefix sum이란게 무엇인가 하면, 다음과 같다. $a_1$부터 $a_n$까지의 $n$개의 숫자가 늘어서 있을 때, prefix sum 배열..
2013. 7. 29. 23:50