imos 알고리즘

1.   imos 알고리즘이란?

이모스 알고리즘은 구간 값 업데이트를 효율적으로 수행할 수 있는 알고리즘으로, 주로 구간에 일정한 값을 더하거나 빼는 작업을 빠르게 처리할 때 사용된다. 

 

1.1 기본원리

1. 차분 배열 초기화 : 크기 N+1의 배열을 0으로 초기화한다.
2. 구간 업데이트 : 각 업데이트 연산을 통해 차분 배열에 값이 더해지거나 빼진다.
3. 누적 합 계산 : 배열의 누적 합을 계산하여 원래 배열의 값을 구한다.

1.2 예제

Naive하게 For문을 활용한 해법

식당을 방문한 각 고객 i(명에 대해 입장시간 S_i와 퇴장시간 E_i가 주어진다. (0 <= i < C), (0 <= S_i < E_i <= T) 

가게에 가장 많은 손님이 있었던 때의 손님의 수 M은 몇일까?  

(단, 같은 시간에 퇴장과 입장이 있을 경우 퇴장이 선행된다고 가정한다.)

 

 

 

time_list = [[0,3],[2,6], [5,7], [4,10]]
n = 4
answer_list = [0 for _ in range(10)]

for i in range(n):
  # 각각의 사람에 대해서 입장시간부터 퇴장시간까지에 해당되는 answer_list 인덱스값에 +1
  for j in range(time_list[i][0], time_list[i][1]):
      answer_list[j] += 1

print(answer_list)

M = max(answer_list)
answer = answer_list.index(M)
print(answer)

# 출력 결과
# [1, 1, 2, 1, 2, 3, 2, 1, 1, 1]
# 5

 

위 문제를 나이브하게 풀면 그림과 같이 생각하여 for문으로 풀 수 있다. for문으로 풀게 되면 O(CT)의 시간복잡도를 가지게 된다.하지만 imos 알고리즘을 활용하게 되면 더욱 빠르게 처리할 수 있다.

 

imos 알고리즘을 활용한 해법

imos 알고리즘에서는 입장시간에 +1을 퇴장시간에 -1을 기록해 두고 구간 업데이트 후 누적합을 계산하면 된다.

구간 업데이트에는 O(C), 누적합 계산에는 O(T)의 시간이 걸려 총 O(C+T)의 시간복잡도를 가지게 된다. 

time_list = [[0,3],[2,6], [5,7], [4,10]]
n = 4
answer_list = [0 for _ in range(10 + 1)]

# 구간 업데이트
for i in range(n):
  answer_list[time_list[i][0]] += 1
  answer_list[time_list[i][1]] -= 1

# print(answer_list)  # [1, 0, 1, -1, 1, 1, -1, -1, 0, 0, -1]

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

print(answer_list)

# 최대로 겹친 구간 찾기
M = max(answer_list)
answer = answer_list.index(M)
print(answer)

# 출력 결과
# [1, 1, 2, 1, 2, 3, 2, 1, 1, 1, 0]
# 5

 

2. 다차원에서의 imos 알고리즘

이모스 알고리즘은 다차원에서 보다 유용하다. 보다 자세한 예제는 추후에 작성하는 걸로...

아래 참고자료 링크에서도 확인할 수 있다. 

 

---

참고자료

[1] ImosLab

[2] 누적합의 확장, imos법