기록방

💡 합의 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특한 목적의 알고리즘 🚀 합의 배열 S 정의 구간 합 알고리즘을 활용하려면 먼저 합 배열을 구해야 한다. A[ 0 ]부터 A[ i ]까지의 합 : S[ i ] = A[ 0 ] + A[ 1 ] + A[ 2 ] + ... + A[ i-1 ] + A[ i ] 합 배열은 기존의 배열을 전처리한 배열 합 배열을 미리 구해 놓으면 기존 배열의 일정 범위의 합을 구하는 시간 복잡도가 O(N)에서 O(1)로 감소 A[ i ] 부터 A[ j ] 까지의 배열 합을 합 배열 없이 구하는 경우, 최악은 i가 0이고 j가 N인 경우로 O(N) 합 배열을 이용하면 O(1) 🚀 합 배열 S를 만드는 공식 S[ i ] = S[ i-1 ] + A[ i ] 🚀 구간 합을 ..