[알고리즘] 이모스법 (Imos Method)

이모스 법(Imos Method)이란?

이모스법은 누적 합 알고리즘을 다차원, 다차수로 확장한 것을 의미한다. 

https://imoz.jp/algorithms/imos_method.html

いもす法

---

1차원 이모스 법

• 구간 [l, r)에 x를 더하는 쿼리를 처리할 때, 배열 d에 d[i] += x, d[r] -= x를 처리한다. 
• 모든 쿼리를 처리한 후 배열 d에 대해 누적 합을 구하면 원래 배열의 각 위치에 대해 더해진 값을 구할 수 있다. 
• O(N+Q)로 효율적이다. 

 

예시) 손님 수 구하기

문제

식당을 방문한 각 고객의 입장 시간과 퇴장 시간이 주어진다. 같은 시간에 가게에 있던 손님의 수의 최대는 몇 명인가?

손님이 아래와 같이 방문했다고 가정하자

시간	0	1	2	3	4	5	6	7	8	9
1번	O	O	O
2번			O	O	O	O
3번						O	O
4번									O

 

1. 나이브하게 구하기

s = [0, 2, 5, 8] # 손님 i의 입장시간 s[i]
e = [3, 6, 7, 9] # 손님 i의 퇴장시간 e[i]

C = 4 # 손님의 수
T = 10 # 시간

table = [0 for _ in range(T)]   # 0 ~ T 시간대의 정보를 기록하기 위한 테이블

# 각 손님에 대해 입장시간 ~ 퇴장시간까지 해당되는 table의 인덱스 +1
for i in range(c):
	for j in range(s[i], j[i]):
    	table[j] += 1
        
print(max(table))

위 경우에는 시간 복잡도는 O(CT)이다. 

 

2. 이모스법으로 구하기

이모스 법의 아이디어는 시작점과 끝점만을 기록하는 데에 있다. 시작점에는 +1, 끝점에는 -1을 기록한후, 
이후에 누적합을 구하여 답을 구한다. 

s = [0, 2, 5, 8] # 손님 i의 입장시간 s[i]
e = [3, 6, 7, 10] # 손님 i의 퇴장시간 e[i]

C = 4 # 손님의 수
T = 10 # 시간

table = [0 for _ in range(T+1)]

for i in range(c):
    table[s[i]] += 1
    table[e[i]] -= 1

# table : [1, 0, 1, -1, 0, 1, -1, -1, 1, -1, 0]

# 누적 합 계산
for i in range(1, len(table)):
	table[i] = table[i-1] + table[i]

# prefix : [1, 1, 2, 1, 1, 2, 1, 0, 1, 0, 0]

print(max(table)) # 2

 

위 경우에는 구간 업데이트에 O(C), 누적 합 계산에 O(T)
따라서 총 O(C+T)의 시간 복잡도를 가진다. 

 

2차원 이모스 법

이모스 법은 고차원으로의 확장이 용이하다. 

 

예시 ) 몬스터의 종류

문제

서로 다른 잔디 위에는 각각 한가지 종류의 몬스터가 나타난다. (잔디가 겹치면 여러 몬스터 출몰 가능) 몬스터는 범위 밖에서는 나오지 않는다. 효율적인 진행을 위해 하나의 타일에서 나타나는 몬스터의 종류의 최대치를 구하려고 한다. 

몬스터가 나오는 사각형(빨간색)과 몬스터 종류의 수

 

1. 나이브하게 구하기

# 2D 배열 초기화
tiles = [[0 for x in range(W)] for y in range(H)]

# 몬스터 출현 처리
for i in range(N):
    # 몬스터 i가 나타나는 [(A[i],C[i]), (B[i],D[i]))의 범위에 1을 더한다
    for y in range(C[i], D[i]):
        for x in range(A[i], B[i]):
            tiles[y][x] += 1

# 최대값 확인
tile_max = max(max(row) for row in tiles)

 

각 몬스터가 나타나는 범위에 포함된 모든 타일에 1을 더해 구할 수 있다. 

이 경우에는 O(NWH)의 시간 복잡도를 가진다. 

 

2. 이모스법으로 구하기

 

앞서 1차원에서는 시작지점에 +1, 끝 지점에 -1을 하고 누적합을 구하여 우리가 구하려는 영역을 복구하였다. 

 

위 방식을 2차원 공간에도 적용해보자

2차원 공간은 1차원에서 y축 방향으로 늘어난 만큼 x축으로 누적합을 구하고, 그 다음 y축으로 누적합을 구하면 된다. 

우리가 구하고자 하는 사각형의 영역이 위와 같다고 하자.  두 번의 누적합 연산을 통해 위 모양이 나오게 하려면 어떻게 해야할까?

위와 같은 방법으로 셋팅하면 우리가 원하는 결과를 얻을 수 있다. 

 

먼저 x축 방향으로 누적합을 구하고

그 다음 y축 방향으로 누적합을 구해주면 우리가 원하는 결과의 모양이 나오게 된다!

 

이러한 모양을 찍고자 한다면 어떻게 하면 될까?

초기 가중치를 셋팅해두고 가로방향 누적, 세로방향 누적을 수행하면 우리가 원하는 결과를 얻을 수 있다. 

# 2차원 배열 초기화
tiles = [[0] * W for _ in range(H)]

# 가중치 추가
for i in range(N):
    tiles[C[i]][A[i]] += 1
    tiles[C[i]][B[i]] -= 1
    tiles[D[i]][A[i]] -= 1
    tiles[D[i]][B[i]] += 1

# 가로 방향 누적 합
for y in range(H):
    for x in range(1, W):
        tiles[y][x] += tiles[y][x-1]

# 세로 방향 누적 합
for y in range(1, H):
    for x in range(W):
        tiles[y][x] += tiles[y-1][x]

# 최대값 찾기
tile_max = 0
for y in range(H):
    for x in range(W):
        if tile_max < tiles[y][x]:
            tile_max = tiles[y][x]

 

가중치 업데이트 : O(N)

초기화 , 가로방향 누적, 세로방향 누적, 최대 값 찾기 : O(H * W)

 

최종적인 시간 복잡도 : O(H * W * N)