SMALL 구간합#합배열#알고리즘#백준#java1 구간 합 ( 핵심이론 ) 구간 합은 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘 구간 합의 핵심 이론 구간 합 알고리즘을 활용하려면 먼저 합 배열 구하기 합 배열 S 정의 S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A[i] //A[0]~A[i]까지의 합 합 배열은 기존의 배열을 전처리한 배열 미리 구해놓으면 일정 범위의 합 구하는 시간 복잡도가 O(N) → O(1) 합 배열 S 만드는 공식 S[i] = S[i-1] + A[i] 구간 합을 구하는 공식 2023. 6. 16. 이전 1 다음 반응형 LIST