imos법 이해하기

개인 기록용 느낌으로 글을 쓰기 때문에 나만의 해석이 첨가되어 있다

imos법이 뭔지에 대해선 나보다 훨씬 설명 잘 하는 사람들이 많으니 그사람들 글을 보기 바란다

 

이 글은 imos법이 다양한 문제에 활용되는 모습을 보면서, 그에 대한 내 고찰을 다룬다

 

imos법에 대한 내 생각은 누적합의 확장된 버전이라는 것이다

n차원 공간에서 쿼리를 처리할 때

그 구간의 시작점과 끝점만 기록해준 뒤, 마지막에 O(N)정도로 후처리를 해주면 그 쿼리 결과를 개빠르게구할수있다는 거였음

그 대표적인 문제들은 아래와 같다

https://www.acmicpc.net/problem/3020

https://school.programmers.co.kr/learn/courses/30/lessons/92344

https://www.acmicpc.net/problem/16436

 

---

근데 이 문제의 경우 imos법을 쓸 수 있다는 생각도 못했다

imos법에 대한 다른 해석이 필요해 보인다

https://atcoder.jp/contests/abc338/tasks/abc338_d

D - Island Tour

 

문제 요약 : 

N개 섬이 순차적으로 원형으로 이어져 있고, N-1개 다리로 연결되어 있음

섬에서 섬으로 가는 비용은 1임

길이가 M인 수열이 주어짐. 이 순서대로 섬들을 방문할 거임

그런데, 우리는 임의적으로 다리 하나를 골라서 잘라버릴 거임. 이때 적절히 다리를 잘랐을 때 방문 비용의 최솟값을 고르시오

 

문제 이해:

총 N개의 섬이 있다고 할 때, 섬 A에서 B로 갈 때 그 비용은

A<B인 경우

B-A 또는 N-B+A일 것이고, 이때 더 작은 값을 취할수록 유리할 것임

다음 섬으로 진행할 때의 선택지는 2가지일 테니까(시계방향으로 가느냐 반시계방향으로 가느냐)

총 가능한 가짓수는 2^M가지일 거고, 이진 트리 모양으로 쭉~ 나올 거고, 다리 하나를 자르게 된다면 그 이진 트리를 가지치기 하는 형식으로 문제가 풀린다고 생각했음

근데 imos법을 이용해 풀린다고 한다

 

에디토리얼 해석:

다음 섬으로 진행할 때의 선택지는 총 2가지임. A , A+1, A+2 ... B로 가거나, A,A-1,A-2,...1...N...B+1,B로 가거나

이 두 경우를 집합 S와 T로 놓으면, 둘 사이엔 교집합이 없고 합집합은 모든 섬들이다

( Here, S and T do not have common elements, and their union equals the entire set of bridges. )

 

집합 S에 속하는 다리를 자를 경우 무조건 T의 크기만큼 이동해야 한다

집합 T에 속하는 다리를 자를 경우 무조건 S의 크기만큼 이동해야 한다

이것을 각각의 원소에 직접 더해 주어도 되지만, 비효율적이다 (M-1번의 연산을 N개 섬들에 대해 하게 될 것이다)

 

그러므로 imos법을 사용해 일차원 배열에 시작과 끝만 기록하고, 마지막에 누적합을 구하는 방법으로 하면

O(M-1) + O(N)이니깐 대충 O(N)의 시간복잡도로 풀린다

 

고찰:

그렇다면 imos법을 어떻게 이해하는게 맞을까

어쨌든 골자는, 1) 어떤 문제를 배열로 모델링한 뒤 / 2) 구간에 몇번씩 계산해야 하는 걸 시작과 끝만 기록하는 식으로 처리하고 / 3) 마지막에 휩쓸면서 누적합을 구하는 것이다

 

그러기 위해선 주어진 문제에 대해 아래와 같은 순서대로의 판단이 필요하다고 생각한다

1) M번의 쿼리를 처리하는 문제인가? -> imos, 세그트리, 시뮬레이션, 희소행렬

2) 그 쿼리들은 어떤 구간에 대해 주어지는가? -> imos, 세그트리

3) 주어진 상황을 N차원 배열로 모델링 할 수 있는가? -> imos (부분 문제로 바꿀 수 있다면 세그트리)

4) 후처리(누적합하며 휩쓸기) 를 통해 쿼리에 대한 결과를 낼 수 있는가? -> imos

 

+ imos쓰는 문제들을 보면 쿼리(수열의 원소) 가 중간에 바뀌지 않는다. 쿼리가 중간에 바뀐다면 세그트리가맞는듯

+ 이 문제의 경우 이게 최단 거리 문제인지 뭔지 헷갈리기도 했고, 이걸 쿼리로 봐도 되나 모르기도 해서 imos법이라는 풀이는 상상도 못 한 것 같다. imos법은 그렇게까지 메이저하단 생각은 들지 않지만... atcoder에 종종 등장하므로 많이 풀어볼 필요는 있을 것 같다