1. 문제 상황: 구간 업데이트의 도전
- 배열에서 특정 구간의 모든 원소에 값을 더하는 연산을 효율적으로 처리해야 하는 상황을 생각해봅시다.
1.1 구체적인 문제
- 크기가 N인 배열이 주어집니다.
- Q개의 구간 업데이트 쿼리가 주어집니다.
- 각 쿼리는 (L, R, X) 형태: L부터 R까지의 모든 원소에 X를 더함
- 모든 쿼리를 처리한 후 최종 배열을 반환해야 합니다.
- 중간에 배열의 값을 조회하는 연산은 거의 없거나 없습니다.
1.2 브루트 포스 접근
def update_range_brute(arr, left, right, value):
for i in range(left, right + 1):
arr[i] += value
문제점:
- 각 쿼리마다 O(N) 시간이 필요
- Q개의 쿼리를 처리하면 총 O(Q × N) 시간 소요
- 배열이 크고 쿼리가 많으면 매우 비효율적
2. 1차원 차분 배열
2.1 기본 아이디어
- 배열에 구간의 시작과 끝에만 변화를 기록합니다.
- 나중에 누적합으로 원본 배열 복원합니다.
2.2 구현 방법
- 원본 배열보다 1 큰 크기의 차분 배열 생성합니다.
- 구간 업데이트 시:
- 구간 시작점(L)에 값을 더함
- 구간 끝점 다음 위치(R+1)에서 값을 뺌
- 최종적으로 차분 배열의 누적합으로 결과 도출
- 원본 배열과 차분 배열의 누적합을 더해 최종 결과 도출합니다.
2.3 동작 원리 상세 설명
- 차분 배열이 작동하는 핵심 원리는 누적합의 특성을 이용한 것입니다.
- 구간 [L, R]에 값 X를 더하는 과정을 자세히 살펴보겠습니다.
- 누적합은 특정 위치의 변화가 이후 모든 원소에 영향을 준다는 특성이 있습니다.
- 이를 이용해 구간의 시작점(L)에 X를 더하면, L부터 끝까지 모든 원소에 X가 더해집니다.
- 구간의 끝점 다음(R+1)에 -X를 더하면, R+1부터 끝까지 모든 원소에서 X가 빠집니다.
- 결과적으로 [L, R] 구간에만 정확히 X가 더해지게 됩니다.
- 즉 L부터 영향이 시작되고 R까지 영향을 주기 위해 R + 1에서 영향을 제거하는 것입니다.
- 이러한 원리 때문에 구간 업데이트를 단 두 번의 연산만으로 처리할 수 있고, 최종적으로 누적합을 계산하면 원하는 결과를 얻을 수 있는 것입니다.
3. 2차원 차분 배열
3.1 개념 확장
- 2차원 배열에서도 차분 배열의 개념을 확장할 수 있습니다.
- 직사각형 영역의 업데이트를 O(1) 시간에 처리할 수 있습니다.
3.2 상세 예제
1단계: 원본 행렬
[
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]
2단계: (0,0)부터 (1,1)까지 영역에 5를 더하는 차분 배열
[
[+5, 0, -5, 0], # (0,0)에 +5, (0,2)에 -5
[ 0, 0, 0, 0],
[-5, 0, +5, 0], # (2,0)에 -5, (2,2)에 +5
[ 0, 0, 0, 0]
]
3단계: 차분 배열의 누적합
[
[5, 5, 0, 0],
[5, 5, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0]
]
4단계: 원본 배열과 더한 최종 결과
[
[6, 7, 3], # 1+5, 2+5, 3+0
[9, 10, 6], # 4+5, 5+5, 6+0
[7, 8, 9] # 7+0, 8+0, 9+0
]
각 단계별 설명:
- 원본 행렬: 초기 상태
- 차분 배열: 영역의 각 모서리에 적절한 값을 배치
- 시작점 (0,0): +5
- 우측 경계 다음 (0,2): -5
- 하단 경계 다음 (2,0): -5
- 대각선 경계 다음 (2,2): +5
- 차분 배열 누적합: 행과 열 방향으로 누적합 계산
- 최종 결과: 원본 배열과 차분 배열의 누적합을 더해서 계산
4. 시간 복잡도 분석
4.1 1차원 배열
- 차분 배열 생성: O(N)
- 구간 업데이트: O(1)
- 최종 배열 복원: O(N)
- 총 시간 복잡도: O(Q + N)
- Q는 쿼리의 개수, N은 배열의 크기
4.2 2차원 배열
- 차분 배열 생성: O(N×M)
- 영역 업데이트: O(1)
- 최종 배열 복원: O(N×M)
- 총 시간 복잡도: O(Q + N×M)
- Q는 쿼리의 개수, N과 M은 배열의 크기
5. 장단점
5.1 장점
- 구간/영역 업데이트가 O(1)로 매우 빠름
- 메모리 사용량이 원본과 거의 동일
- 여러 업데이트를 효율적으로 처리
- 2차원으로 자연스럽게 확장 가능
5.2 단점
- 중간 조회가 비효율적
- 구현이 다소 복잡할 수 있음
- 범위 체크가 중요함
6. 마치며
- 차분 배열은 1차원, 2차원 모두에서 강력한 최적화 도구입니다.
- 특히 여러 번의 구간/영역 업데이트가 필요한 상황에서 탁월한 성능을 보여줍니다. 상황에 맞게 적절히 활용한다면 프로그램의 성능을 크게 향상시킬 수 있습니다.