Prefix Sum 알고리즘이란?문제를 풀다 보면 배열에서 특정 구간의 합을 구해야 하는 문제들을 종종 만나곤 한다. 한 번만 계산해야 한다면 반복문을 통해 \(O(N)\)의 시간 복잡도로 해결할 수 있지만, 여러 번 반복해서 계산해야 한다면 조금 더 효율적인 알고리즘이 필요하다. 이때 사용할 수 있는 알고리즘이 Prefix Sum이다. Prefix Sum 알고리즘은 배열의 첫 번째 원소부터 각 원소들까지의 합을 미리 계산해두는 알고리즘이다. 예를 들어, 배열 [1, 2, 3, 4, 5]가 있을 때 첫 번째 원소의 Prefix Sum은 1, 두 번째 원소의 Prefix Sum은 1 + 2 = 3, 세 번째 원소의 Prefix Sum은 1 + 2 + 3 = 6 이 된다. 이렇게 미리 배열의 모든 원소들의..
