[ 알고리즘 ] 구간 합 (Prefix Sum)
구간 합 이란? 구간 합은 합배열을 이용하여 특정 구간까지의 합을 구하는 알고리즘(시간 복잡도를 더 줄이기 위함) 합배열 공식 ▶ s[ i ] = s[ i - 1 ] + A[ i ] 구간 합 공식 합배열을 먼저 구해놓고, 공식 적용 ▶ s[ j ] - s[ i - 1 ] [예제] A[2] ~ A[5] 까지의 합을 구하세요. ① 위의 합배열에서 공식을 대입 ② 답 → S[5] - S[1] = 45 ③ 풀이 → S[5]가 의미하는 것은? → A[0] ~ A[5] 의 합 → S[1]가 의미하는 것은? → A[0] ~ A[1] 의 합
코딩테스트/[ 알고리즘 ]
2024. 3. 9. 16:49
