알고리즘 문제 해결, 특히 코딩 테스트나 대규모 데이터 분석에서 '구간 합(Range Sum)'을 구하는 문제는 매우 빈번하게 출제됩니다. $N$개의 데이터가 있을 때, 특정 구간의 합을 매번 반복문으로 계산하면 $O(N)$의 시간이 소요됩니다. 만약 이러한 질의(Query)가 $M$번 반복된다면 전체 시간 복잡도는 $O(N \times M)$이 되어, 데이터가 조금만 커져도 '시간 초과(Time Limit Exceeded)'를 피할 수 없습니다. 이때 필요한 기법이 바로 누적 합(Prefix Sum)입니다. 데이터를 미리 가공해 놓음으로써, 아무리 넓은 구간이라도 단 한 번의 연산($O(1)$)으로 합계를 구해내는 이 강력한 알고리즘의 1차원 및 2차원 배열 적용법을 완벽하게 정리해 드립니다.
1. 1차원 구간 합 (1D Prefix Sum)의 원리
누적 합의 핵심 아이디어는 '처음부터 현재 위치까지의 합'을 미리 계산하여 저장해 두는 것입니다. 이를 통해 특정 구간의 합을 단순 뺄셈 연산으로 변환할 수 있습니다.
1-1. 정의 및 공식
원본 배열을 $A$, 누적 합 배열을 $P$라고 할 때, $P[i]$는 다음과 같이 정의됩니다.
- 정의: $P[i] = A[0] + A[1] + ... + A[i]$
- 점화식: $P[i] = P[i-1] + A[i]$ (단, $P[-1] = 0$)
이를 이용해 인덱스 $L$부터 $R$까지의 합($S$)을 구하는 공식은 다음과 같습니다.
- 구간 합 공식: $S(L, R) = P[R] - P[L-1]$
즉, $0$부터 $R$까지의 총합에서, 구간에 포함되지 않는 $0$부터 $L-1$까지의 합을 빼는 원리입니다.
2. 2차원 구간 합 (2D Prefix Sum)의 원리
이미지 처리나 격자(Grid) 형태의 데이터에서 직사각형 영역의 합을 구할 때 사용됩니다. 1차원보다 복잡해 보이지만, '포함 배제의 원리(Inclusion-Exclusion Principle)'만 이해하면 간단합니다.
2-1. 2차원 누적 합 배열 생성 (채우기)
2차원 배열 $P[i][j]$는 $(0, 0)$부터 $(i, j)$까지의 사각형 영역의 전체 합을 의미합니다.
- 생성 공식:
$P[i][j] = A[i][j] + P[i-1][j] + P[i][j-1] - P[i-1][j-1]$
위쪽($P[i-1][j]$)과 왼쪽($P[i][j-1]$)의 누적 합을 더하면 대각선 부분($P[i-1][j-1]$)이 두 번 더해지므로, 한 번 빼주는 것이 핵심입니다.
2-2. 2차원 구간 합 구하기 (쿼리)
$(x1, y1)$부터 $(x2, y2)$까지의 직사각형 구간 합을 구하려면, 전체 큰 사각형에서 불필요한 영역을 빼고 중복해서 뺀 영역을 다시 더해줍니다.
- 최종 공식:
$Sum = P[x2][y2] - P[x1-1][y2] - P[x2][y1-1] + P[x1-1][y1-1]$
3. 파이썬(Python) 구현 코드 (팁 포함)
구현 시 가장 큰 골칫거리는 인덱스가 0보다 작아지는 경우(IndexOutOfRange)를 처리하는 것입니다. 이를 방지하기 위한 '패딩(Padding) 기법'을 소개합니다. 배열의 크기를 $N+1$로 잡고 0번 인덱스를 비워두면, 별도의 `if` 문 없이 깔끔하게 구현할 수 있습니다.
# 1. 1차원 배열 구간 합 예제
def prefix_sum_1d(arr, queries):
n = len(arr)
# 패딩을 사용하여 인덱스 계산 단순화 (0으로 채워진 N+1 크기)
prefix = [0] * (n + 1)
# 누적 합 생성 O(N)
for i in range(n):
prefix[i+1] = prefix[i] + arr[i]
results = []
for l, r in queries:
# l, r은 1-based index라고 가정 (아니라면 조정 필요)
# 공식: P[R] - P[L-1]
range_sum = prefix[r] - prefix[l-1]
results.append(range_sum)
return results
# 2. 2차원 배열 구간 합 예제
def prefix_sum_2d(matrix, x1, y1, x2, y2):
row = len(matrix)
col = len(matrix[0])
# N+1 x M+1 크기의 누적 합 배열 생성
p = [[0] * (col + 1) for _ in range(row + 1)]
# 누적 합 채우기 O(N*M)
for i in range(1, row + 1):
for j in range(1, col + 1):
p[i][j] = matrix[i-1][j-1] + p[i-1][j] + p[i][j-1] - p[i-1][j-1]
# 구간 합 계산 O(1)
# 입력받은 좌표도 1-based라고 가정
return p[x2][y2] - p[x1-1][y2] - p[x2][y1-1] + p[x1-1][y1-1]
# 테스트 데이터
data = [10, 20, 30, 40, 50]
query_list = [(1, 3), (2, 5)] # 1번째~3번째, 2번째~5번째 합
print(f"1D Result: {prefix_sum_1d(data, query_list)}")
1. 성능 혁신: 반복문을 사용하면 $O(N)$인 구간 합 계산을 전처리 과정을 통해 $O(1)$로 획기적으로 단축합니다.
2. 1차원 공식: $Sum(L, R) = P[R] - P[L-1]$ (끝 구간 누적 합 - 시작 전 구간 누적 합)
3. 2차원 공식: 포함 배제의 원리를 적용하여, 중복해서 더해지거나 빠진 대각선 영역을 보정하는 것이 핵심입니다.