imos
-
누적합의 확장 IMOSComputer/CS 2021. 9. 30. 01:11
IMOS는 누적합의 개념으로 특정 구간에서 가장 많이 중첩되는 영역을 구할 수 있는 방법 중 하나이다. 예를 들어 가게에 Q명의 손님이 방문한다. 가게는 시간 0부터 T까지 운영되며, 각각의 손님 i의 방문 시각(si)과 퇴장 시각(ei)이 입력으로 주어진다. 가게 운영 중 손님이 가장 많이 방문했을 때의 손님 수는 몇 명인가? 이런 문제가 있다면 입력을 위와 같은 그림으로 나타낼 수 있을 것이다. 이 때 가장 단순하게 구현한다면 for문을 si부터 ei까지 돌리면서 해당 배열의 값을 +1 해주는 것이겠지만 이 경우는 쿼리 하나의 처리 시간이 T 쿼리의 갯수를 Q라고 했을 때 시간 복잡도는 Q(TQ)가 되어서 쿼리가 많아지고 시간이 길어지는 경우에는 풀 수 없게된다. 이 때 사용하는 IMOS는 입장과 퇴..