구간 합

구간 합

구간 합은 합 배열을 이용해 시간 복잡도를 더 줄이기 위해 사용하는 특수 목적의 알고리즘이다.

 

 

합 배열이란 ?

배열 A가 있다고 했을 때, 합 배열 S[i]는 A[0] ~ A[i]까지 합한 값을 의미한다.

합 배열을 미리 구해놓으면 기존 배열의 일정 범위의 합을 구하는 시간 복잡도가 O(N)에서 O(1)로 감소한다.

 

 

합 배열 S를 만드는 공식

S{i]  = S[i-1] + A[i]

내가 만듦

위와 같은 배열이 있다고 할 때, S[1]은 위 공식에 따라

S[1] = S[0] + A[1]이므로 3 + 6 = 9가 된다.

 

 

 

구간 합을 구하는 공식

배열 A의 i ~ j까지의 구간 합은 다음과 같다.

S[j] - S[i - 1]

직접 제작

만약 배열 A의 2 ~ 4까지의 구간 합을 구한다고 하면 

위 공식에 따라 S[4] - S[2 - 1] = 28 - 9 = 19가 된다.

 

 

 

알고리즘 문제를 풀 때 구간합을 여러번 구하는 문제일 경우 합 배열을 사용하는 것이 좋다.

합 배열은 A 배열의 값이 바뀌지 않는 이상 한번 구해놓으면 변하지 않기 때문에 유용하게 사용이 가능하다.

구하는 방법도 비교적 쉬우므로 잘 이해해서 적재적소에 활용하도록 ...