구간합이란
배열의 처음부터 특정 인덱스까지의 합(누적 합)을 미리 구해놓은 별도의 배열(합 배열)을 이용하여,
특정 구간의 합의 시간복잡도를 O(N)에서 O(1)으로 줄일 수 있습니다.
핵심 공식
1차원 합배열 공식
기존 리스트 A가 있을 때 합 배열 S는 아래와 같은 구조입니다.
S [i] = A [0] + A [1] +... + A [i]
위와 같은 합배열을 좀 더 추상화시키면 아래와 같습니다.
S [i] = S [i-1] + A [i]
1차원 구간합 공식
그렇다면 합배열을 이용해 구간합을 구하는 공식은 어떻게 될까요?
A [2]부터 A [5]까지의 구간합을 구한다고 하면
A [0] ~ A[5] 부터 A[0] ~ A [1]의 차이를 구하는 것과 같습니다.
이는 S [5] - S [1]로 표현할 수 있습니다.
이를 추상화해서
i번째부터 j번째까지의 합을 구한다고 한다면 아래와 같습니다.
S(i, j) = S [j] - S [i-1]
2차원 합배열
2차원 합 배열 공식은 수식으로만 보면 복잡하지만, '넓이 구하기(면적)' 관점에서 보면 매우 직관적입니다.
핵심은 "이미 구해놓은 넓이를 재활용하자"는 것입니다.
A [0,0] ~ A [4,2]를 의미하는 S [4,2]인 녹색영역의 직사각형 넓이(합배열)를 구하려면 어떻게 해야 할까요?
이걸 매번 처음부터 다 더하는 게 아니라, A [4,2]를 기준으로 내 바로 위쪽과 내 바로 왼쪽에 있는 이미 계산된 직사각형들을 합쳐서 만듭니다.
위쪽 직사각형인 S [3,2]와 왼쪽 직사각형인 S [4,1]를 더해주고, 중복되는 영역인 S [3,1]를 빼준다음 A [4,2]만 더하면 됩니다.
이를 식으로 나타내면 아래와 같습니다.
S [4,2] = S [3,2] + S [4,1] - S [3,1] + A [4,2]
이를 추상화하면 아래와 같습니다.
S [i][j] = S [i-1][j] + S [i][j-1] - S [i-1][j-1] + A [i][j]가 됩니다.
2차원 구간합
A [3,3] ~ A [4,4]인 파란색 영역을 구간합으로 구하고 싶으면 어떻게 해야 할까요?
전체 구간합인 S [4,4]에서 주황색 영역인 S [2,4]와 초록색 영역인 S [4,2]를 빼준다음 두 번 빼버린 부분인 S [2,2]를 더 해주면 됩니다.
정리하면 A [3,3] ~ A [4,4] = S [4,4] - S [2,4] - S [4,2] + S [2,2]입니다.
'CS > 자료구조, 알고리즘' 카테고리의 다른 글
| 슈도코드(Pseudocode) (0) | 2025.12.20 |
|---|