[알고리즘] 접두사합(prefix sum) 알고리즘 by javascript (ft. 부분합/구간합)
Prefix Sum(접두사 합) 부분합, 누적합, 구간합 등으로 불리며 해당 합을 빠르게 구하는 알고리즘이다. 사실 알고리즘 치고는 매우 간단하다. 이 알고리즘의 원리는 다음과 같다. 각각의 숫자까지의 합을 미리 계산하여 저장해놓고 그 저장한 값을 활용하여 구간합을 구한다. 사실 접두사합, 구간합, 부분합 알고리즘을 검색하면 많은 블로그가 나올 텐데, 기본적으로 접두사 합 알고리즘의 공식을 다음과 같이 설명하고 있다. P[Right] - P[Left - 1] 크게 틀린 공식은 아니니 일단 이런 식으로 사용하는구나 정도는 알고 진행하면 좋다. 다른 알고리즘도 마찬가지겠지만 문제에 따라 정해진 공식을 사용할 수 없는 경우가 많다. 예를 들어 숫자 [100, 101, 102, 103, 104]가 주어졌다고 가..
2022. 10. 12.