728x90 구간합2 2차원 배열 누적합(합배열) 개념 이해하기 (chatGPT를 통해 정리한 내용입니다.) 1. 2차원 배열 누적합(합배열) 개념1.1. 개념 소개누적합(prefix sum): 1차원 배열에서 특정 구간의 합을 빠르게 구하기 위해 미리 구간의 합을 저장해두는 기법을 말합니다.2차원 배열 누적합: 2차원 배열에서 어떤 직사각형 영역(부분행렬)의 합을 빠르게 구하기 위해 미리 **누적합 배열(dp)**을 만들어 두는 방법입니다.1.2. 왜 사용하는가?문제 상황:"N×M 크기의 배열이 주어지고, Q개의 질의(query)가 주어집니다. 각 질의는 (x1, y1)부터 (x2, y2)까지의 부분행렬에 포함된 원소들의 합을 구하는 문제"직접 합산:매 질의마다 해당 영역을 순회하면 시간 복잡도가 O(N×M)이고, Q가 많을 경우 시간 초과가 발생할 수 있습니다.누.. 2025. 2. 7. 합배열 개념 및 예제(코딩테스트/배열/구간합) (뤼튼을 통해 정리된 내용입니다.) 합배열(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 다음 728x90