[알고리즘] 구간 합(Prefix Sum)

구간 합(Prefix Sum)

 

구간 합이란?

• 구간 합은 한 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘 이다.
• 구간 합 알고리즘을 활용하기 위해 합 배열을 미리 구해야 한다.
• 기존 배열의 범위 합의 구하는 시간 복잡도는 O(N)인데 합 배열을 통해 구하는 시간 복잡도가 O(1)로 감소한다.

합 배열 공식

• S[ i - 1 ] + A[ i ]

구간 합 공식

• S[ j ] + S[ i - 1 ]

구간 합 코드 C++

#include<iostream>

int main()
{
	int A[10] = { 1,2,3,4,5,6,7,8,9,10 };

	int S[10] = {};

	S[0] = A[0];
	std::cout << S[0] << " ";
	for (int i = 1; i < 10; ++i)
	{
		S[i] = S[i  - 1] + A[i];
		std::cout << S[i] << " ";
	}

	std::cout << std::endl;
	// 1 ~ 4 에서 부분합
	// PrefixSum = 14
	int PrefixSum = S[4] - S[1 - 1];
	std::cout << PrefixSum << std::endl;

	// 2 ~ 7 에서 부분합
	// PrefixSum = 33
	PrefixSum = S[7] - S[2 - 1];
	std::cout << PrefixSum;
}