[TIL] 알고리즘 구간 합

✍ Today I Learned

 

구간 합

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

 

합 배열 구하기

출처 : Do It! 알고리즘 코딩테스트 -핵심이론

// 배열 A가 있을 때 합 배열 S의 정의
S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A[i] // A[0]부터 A[i]까지의 합

// 합 배열을 만드는 공식
S[i] = S[i-1] + A[i]

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

 

 

구간 합 구하기

출처 : Do It! 알고리즘 코딩테스트 -핵심이론

// 구간 합 구하는 공식
S[j] - S[i-1] // i에서 j까지 구간 합

// A[2] ~ A[5] 구간 합을 합 배열로 구하는 과정
S[5] = A[0] + A[1] + A[2] + A[3] + A[4] + A[5]
S[1] = A[0] + A[1]
S[5] - S[1] = A[2] + A[3] + A[4] + A[5]

 

 

 

 

※ 이 내용은 Do it! 알고리즘 코딩테스트 - 핵심이론 강의를 듣고 정리한 내용입니다.