시간복잡도1 합배열 개념 및 예제(코딩테스트/배열/구간합) (뤼튼을 통해 정리된 내용입니다.) 합배열(Prefix Sum Array)은 주어진 배열의 특정 구간의 합을 빠르게 계산하기 위한 기법입니다. 이 기법을 사용하면 배열의 특정 인덱스 구간의 합을 O(1) 시간 복잡도로 계산할 수 있도록 도와줍니다.1. 합배열의 개념합배열은 원래 배열의 각 인덱스까지의 합을 저장한 새로운 배열입니다. 예를 들어, 주어진 배열 arr의 합배열 prefixSum은 다음과 같이 정의됩니다:prefixSum[i] = arr[0] + arr[1] + ... + arr[i]2. 합배열의 공식합배열을 사용하여 주어진 배열의 구간 합을 계산하는 공식은 다음과 같습니다:특정 구간 [l, r]의 합:sum(l, r) = prefixSum[r] - prefixSum[l - 1] (단, l >.. 2025. 2. 6. 이전 1 다음