[이론] 구간 합, 합 배열 구하기

구간 합: 시간 복잡도를 줄이는 특수한 알고리즘

구간 합은 특정 구간의 합을 빠르게 구하기 위해 사용되는 알고리즘입니다.
이 알고리즘의 핵심은 "합 배열"이라는 개념을 활용해 계산량을 줄이는 데 있습니다.

 

구간 합이란? 🤔

구간 합은 간단히 말해, 배열 A에서 특정 구간 [ i , j ]의 합을 빠르게 구하는 방법입니다.

예를 들어, 배열 A가 다음과 같다고 가정해보겠습니다.

 

구간 [1, 4] 의 합은 2 + 4 + 1 + 5 = 12 입니다.

하지만 단순히 반복문을 이용해서 계산한다면, 시간 복잡도가 O(N)에 해당할 수 있습니다.
이 과정을 더 빠르게 해결하기 위해 합 배열을 활용합니다.

 

구간 합의 핵심 이론: 합 배열 만들기 📚

합 배열(S)은 배열의 각 위치까지의 누적 합을 저장한 배열입니다.
이를 통해 특정 구간의 합의 시간 복잡도를 O(1)로 구할 수 있습니다.

 

합 배열 S 구하기

 

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

S[4] = A[0] + A[1] + A[2] + A[3] + A[4] = 15

 

합 배열 S를 만드는 공식

 

S[i] = S[i-1] + A[i]
S[4] = S[3] + A[4] = 15

 

구간 합 구하기

i = 2이고, j=4 일 때의 구간 합을 구해보도록 합시다. 😊

A[2] + A[3] + A[4] = 10

 

구간 합 구하기 공식

• S[ j ] - S[ i-1 ]  // i에서 j까지 구간 합

 

	S[4] = A[0] + A[1] + A[2] + A[3] + A[4] = 15
  -	S[1] = A[0] + A[1] = 5
____________________________________________________
	S[4] - S[1] =	     A[2] + A[3] + A[4] = 10

 

이렇게 하면 단순 반복문 대신 O(1) 의 시간 복잡도로 구간 합을 계산할 수 있습니다.

 

결론 ✨

구간 합 알고리즘은 많은 구간 합을 반복적으로 계산해야 하는 문제에서 유용하게 사용됩니다.
이를 통해 효율적으로 시간을 절약하고, 알고리즘의 성능을 높일 수 있습니다.

 

읽어주셔서 감사합니다 🙇