[알고리즘] 구간 합

구간 합

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

(코테에서 사용빈도가 높다..)

 

1.구간 합의 핵심이론

  : 구간 합 알고리즘을 활용하려면 합 배열을 구해야한다. 

 

2. 합 배열 S 정의

  S[i] = A[0] + A[1] + A[2] + A[3] + ... + A[i-1] + A[i]  //A[0] 부터 A[i] 까지의 합 

 

합 배열은 기존의 배열을 전처리한 배열이라고 생각하면 된다. 이렇게 합배열을 미리 구해놓으면 기존 배열의 일정 범위의 합을 구하는 시간 복잡도가 O(N) 에서 O(1) 로 감소한다. (우리는 시간복잡도를 항상 고려해야하기 때문에 시간복잡도가 감소하는쪽으로 계속 생각해야한다!! 명심하자.)

 

3. 합 배열 S를 만드는 공식 

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

 

4. 구간 합을 구하는 공식(i부터 j까지의 합)

 

S[j] - S[i-1]

 

#나만의 설명(내가 이해할려고 쓴 글)

구간 합을 구하려면 합배열을 먼저 구해놓자. 그래야 시간복잡도가 감소한다. 

먼저 합배열을 이해해보자.

15 2 4 34 56 32 -> 이렇게 6개의 숫자가 있다.

인덱스는 0부터 시작하기 때문에, 0번째 인덱스에 있는 숫자는 15이고, 5번째 인덱스에 있는 숫자는 32 이다. 

합배열을 먼저 구해보면, S[5] = S[4] + A[5] 

다음은 구간 합을 구해보자.

예를들어 3번째 인덱스부터 5번째인덱스까지의 숫자들의 합을 구하고싶다면 i=3, j=5 라고하자.

S[j](전체를 더한 합) 에서 구간의 첫 인덱스인 i 의 바로 전인덱스의 숫자 즉, i-1 까지의 합 배열을 빼주면 구간합이 나오게 된다.

따라서, S[j]-S[i-1]이 공식이 된다. 예시를 대입해보면, S[5] - S[2] 가 되겠다. 이해완료!