imos 알고리즘 - 누적합 문제 효율적으로 푸는 방법

개인 공부/알고리즘

imos 알고리즘 - 누적합 문제 효율적으로 푸는 방법

_h.j 2024. 6. 30. 14:00

728x90

imos - 예제 문제 백준 20440 , 백준 3020, 백준 5541, 백준 16436, 카카오 파괴되지 않은 건물

imos (Indexed Modification of Sums)법

특정 구간을 빠르게 업데이트하고, 이를 통해 누적합을 구할 때 유용한 알고리즘
핵심은 업데이트 구간을 배열에 기록 후, 누적 합을 통해 최종 값을 계산
이외에서 육각형 좌표계 등 다양한 특수 좌표계에서 써먹을 수 있다.
수직선 위에 선을 여러 개 그어서, 가장 선이 많이 겹치는 부분 찾는 것

정해진 구간 내에서 시작과 끝이 포함된 부분 집합에 대한 명령이 여러 개 들어올 때, 반복적으로 연산하게 되면 연산 시간이 매우 커질 수 있다. O(QN)

상황 예시를 들어보면,

아래는 0 ~ 16 시 까지 한 장소에 대해 N명의 사람이 입장과 퇴장을 반복할 때, 각 시간에 대해 장소에 존재했던 사람이 몇명인지 구하는 상황. → imos 사용하지 않고 각 입장 퇴장 시간에 대해 반복문으로 연산하면 터진다.

구현

"입장과 퇴장만 기록한다"

각 명열에 대해 시작점과 끝점만 설정해 준 뒤, 마지막에 한 번의 반복을 통해 값을 계산. T(Q + N)

1차원 배열에서 구현

백준 3020,

각 시간에 대한 1차원 배열 생성하고 값을 0으로 초기화
각 입장, 퇴장에 대해 +1 , -1

만약 A(1시 ~ 4시), B(2시 ~ 8시), C(3시 ~ 12시), D(4시 ~ 8시) 동안 장소에 있었다면 배열의 값은

[0,1,1,1,0,0,0,0,-2,0,0,-1] 이 된다.

이 배열에 대해 for 돌리며 누적한다.

[0,1,2,3,3,3,3,3,1,1,1,0] 이 된다.

int imos[] = {0,1,1,1,0,0,0,0,-2,0,0,-1};
int sum = 0;
for (int& e : imos) {
	sum += e;
	e = sum;
}

2차원 배열에서의 구현

카카오 파괴되지 않은 건물

2차원 배열의 경우 격자 보드에 사각형 그리기

imos법은 특성상 고차원으로 확장이 용이하다.

$𝐻×𝑊 $ H×W 크기의 격자 보드가 있다. 각 칸의 초깃값은 모두 0이다.
다음과 같은 쿼리 $𝑄Q$개 들어온다.
$x1 y1 x2 y2 $ :
$𝑦1≤ℎ≤𝑦2y1≤h≤y2$ , $𝑥1≤𝑤≤𝑥2x1≤w≤x2$ 에 해당하는 모든 칸
(ℎ, 𝑤)(h, w) 의 값에 1을 더한다.
쿼리를 모두 처리한 뒤의 최종 보드의 상태를 출력하라.

나이브하게 푼다면 매 쿼리마다 해당 사각형 영역에 1씩 다 더한다. → O(QHW)

2차원 imos 배열의 경우 각 꼭지점에 대해

1. 사각형이 시작하는 부분 (왼쪽 위 점) : +1
2. 시작 부분에서 가로, 세로로 나아갔을 때 범위가 끝나는 부분 (빨간색 표시 지점) : -1
3. 사각형이 끝난 부분 (구간 밖 오른쪽 아래 점) -1 해준 걸 상쇄하기 위해 다시 : +1