8. 구간합

구간 합

• 정의: 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수 목적 알고리즘

코딩 테스트에서 사용 빈도가 높음

 

합 배열

개념

• 정의: 기존 배열 누적 합을 저장하는 배열
  • S[i] = A[0] + A[1] + ... A[i]
• 목적: 구간 합에 대한 시간 복잡도를 줄이기 위해
  • 기존: for문을 이용해 구간 합 구함 -> O(N)
  • 해당 기술: 공식을 통해 한번에 구함 -> O(1)

 

합 배열 생성

S[i] = S[i-1] + A[i] 공식 활용

• i-1을 사용하기에 배열 첫 시작 인덱스는 1로 설정
  • 즉, 배열의 크기를 n+1로 선언

int[] S = new int[N+1] //배열 크기 +1 처리

//1번째 인덱스 부터 시작
for(int i=1; i<=N; i++){
	S[i] = S[i-1] + <입력값>;
}

 

 

구간 합 구하기

left ~ right 까지 구간 합 = S[right] - S[left-1]

int result = S[right] - S[left-1];