누적 합(Prefix Sum)

누적 합 ?

• 배열 또는 리스트 등에서 일정 구간의 합을 빠르게 계산하기 위한 방법이면서, 동적 계획법(DP)의 형태 중 하나라고 한다.

• 각 요소까지의 누적 합을 계산하여 이를 배열에 저장해두는 것이 기본적인 방식이다.

어떤 경우에 사용하면 좋을까 ?

• 특정 구간의 합을 구해야 하는 경우 ! → 해당 구간의 끝 지점까지의 누적합에서 시작 지점까지의 누적합을 빼주면 된다.

• 이 알고리즘은 주어진 배열 또는 리스트의 요소가 고정되어 있을 때 구간 합을 반복적으로 계산해야 하는 경우 유용하게 사용될 수 있다.

알고리즘 문제: 연속 부분 수열 합의 개수

• 자연수들로 원형 수열이 주어졌을 때, 연속된 부분 수열의 합이 몇 가지가 나올 수 있는지 구하는 문제이다. ( ex: 1, 4, 3, 2, 5라는 원형 수열에서 1, 4, 3, 2, 3, 2, 5와 같이 합이 같은 부분 수열들이 나타날 수 있다.