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

 

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

 

 

imos (Indexed Modification of Sums)법

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

 

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

상황 예시를 들어보면,

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

백준 2240 문제 그림

 

구현

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

각 명열에 대해 시작점과 끝점만 설정해 준 뒤, 마지막에 한 번의 반복을 통해 값을 계산. 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

4곳 표시 후 가로 쓸어 누적, 세로 쓸어 누적

 

특수 좌표계 imos

삼각형 형태인 경우 아래와 같이 진행 

타겟

 

값 찍고, 가로, 세로, 대각선 쓸기 진행

 

 

 

 

참고

https://driip.me/65d9b58c-bf02-44bf-8fba-54d394ed21e0 

https://velog.io/@nkrang/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-imos-%EB%B2%95