😎 차분배열 (Difference Array Technique)
이 기법은 주로 누적합과 함께 사용되며, 배열의 연속적인 부분에 대한 업데이트를 빠르게 수행할 수 있도록 해준다.
- 효율적인 업데이트 : 배열의 큰 구간을 한번의 연산으로 업데이트할 수 있다. 이는 구반에 포함된 각 요소를 개별적으로 업데이트 하는 것보다 훨씬 빠르다.
- 시간 복잡도 : 각 업데이트는 O(1) 시간에 수행된다. 전체 배열에 대한 누적합 계산은 O(N)시간이 소요된다.
👍 변화의 시작과 끝만을 표시하여 O(1)시간에 업데이트를 수행하고, 차분 배열을 누적하여 각 위치에 최종 변화량을 계산하면 된다.
🧐 응용
- 구간 업데이트가 많은 문제에 적용 가능
- 원본 배열을 직접 수정하지 않고 변화만 기록
구현 시 주의사항
- 인덱스 관리
- 배열 크기 설정 (N+1, 또는 N+2)
문제 해결 과정
- 입력 받기
- 차분 배열 생성 및 업데이트
- 누적합 계산
- 원래 값에 변화량 적용
예시: 학교 도서관 책 대여
상황: 10일 동안의 도서관 책 대여 기록을 관리합니다. 초기에는 모든 날짜에 0권의 책이 대여되어 있습니다.
일 : 1 2 3 4 5 6 7 8 9 10
대여 : 0 0 0 0 0 0 0 0 0 0다음과 같은 대여 작업이 수행된다.
명령어
2일부터 5일까지 매일 3권씩 대여됩니다.
4일부터 7일까지 매일 2권씩 추가로 대여됩니다.
3일부터 8일까지 매일 1권씩 반납됩니다.
차분 배열 기법 적용
차분 배열에 변화를 적용할 때는
1. 변화가 시작되는 지점에 +변화량
2. 변화가 끝나는 지점 + 1에 -변화량
적용하면 된다.
초기 차분 배열 설정
일 : 1 2 3 4 5 6 7 8 9 10 11
차분 : 0 0 0 0 0 0 0 0 0 0 0각 작업 적용
a. 2일부터 5일까지 3권씩 대여:
일 : 1 2 3 4 5 6 7 8 9 10 11
차분 : 0 3 0 0 0 -3 0 0 0 0 0b. 4일부터 7일까지 2권씩 추가 대여:
일 : 1 2 3 4 5 6 7 8 9 10 11
차분 : 0 3 0 2 0 -3 0 -2 0 0 0c. 3일부터 8일까지 1권씩 반납:
일 : 1 2 3 4 5 6 7 8 9 10 11
차분 : 0 3 -1 2 0 -3 0 -2 1 0 0누적 합 계산
일 : 1 2 3 4 5 6 7 8 9 10 11
차분 : 0 3 -1 2 0 -3 0 -2 1 0 0
누적 : 0 3 2 4 4 1 1 -1 0 0 0최종 대여 상태 계산 (초기 상태 + 누적 변화)
일 : 1 2 3 4 5 6 7 8 9 10
최종 : 0 3 2 4 4 1 1 0 0 0결과 해석
2일: 3권 대여
3일: 3권에서 2권으로 감소 (1권 반납)
4일: 2권에서 4권으로 증가 (2권 추가 대여)
5일: 4권 유지
6일-7일: 1권으로 감소 (2권 대여 종료, 계속 1권씩 반납)
8일 이후: 모든 책 반납
이 예시는 여러 작업이 겹치는 경우에도 차분 배열 기법이 어떻게 효과적으로 작동하는지 보여준다. 각 단계에서의 변화가 누적되어 최종 결과에 반영된다.
활용
차분 배열 기법 ( 누적합 활용 )은
구간 업데이트가 많은 경우 (문제 풀 때 N^2을 막은 경우)
누적 효과를 계산해야 하는 경우 (여러 변화가 중첩되어 최종 결과를 구해야 할 때)
카운팅이나 합계를 효율적으로 계산해야 할 때 (특정 범위의 합계나 카운팅을 자주 구해야 하는 경우)
이럴 때 자주 사용한다.
-> 이 기법의 주요 장점은 시간 복잡도 상으로 업데이트 작업은 O(1), 전체 계산은 O(N)으로 끝난다.
