imos 법 (いもす 法, imos 法) 에 대한 간략한 소개 및 설명.

이번 주제는

문제풀이에 도움이 될만한 기초적인 알고리즘,

imos(이모스) 법 이라고 불리는 것 입니다.

 

왜 불리는 것 이냐면,

잠깐 찾아본 바로는

이것에 대한 정의가 명확히 없고,

 

원래부터 개발자들이

본능적으로 효율적인 코드를 짜다보니,

굳이 명명하지 않아도 이런식으로

코드를 짜는 게 흔한 일이었는데,

 

어느날 imos( いもす) 라는 닉네임을 가진

일본의 블로거(개발자) 가 이것에 대해

정확히 서술했다~ 라는 썰을 읽었습니다.

 

사실인진 모르겠고,

 

그래서 이 이모스가 무슨뜻인지 궁금해서,

일본에서 오래 살고,

거기서 대학까지 나온 친구에게

いもす 의 뜻을 물어보았습니다.

그렇다고 합니다.

그냥 닉네임을 "모지리" 정도로 지은건가 봅니다.

 

서론은 이만 하고,

이제 imos 법을 설명하겠습니다.

 

만약, 어떠한 범위를 가진 좌표가

랜덤하게 동적으로 주어질때,

그 좌표의 범위 내에 해당하는 값들이

서로 겹치는 부분의 합을 구하고 싶다면,

 

저처럼 초보이신 분들은,

 for 문과 if 문을 사용해서

어떻게든 풀어보려고 할것입니다.

 

물론 두가지를 사용해서 푸는것도 맞는데,

초보라 도저히 식이 떠오르지 않습니다.

 

그럴때 imos 법을 학습해보면

해결책이 될 수도 있습니다.

 

imos 법은 일반적으로,

 

전체 범위의 좌표를 하나 생성하고,

각 좌표의 [시작점]에+1,

좌표의 [끝점+1]에

-1의 값을 매김으로써

각 좌표들의 범위를

전체크기의 좌표 안에 체크해놓고,

 

이 상태에서 for문을 1번만 써서

최소한의 시간복잡도(컴퓨터의 연산 시간) 로 

겹쳐진 좌표의 범위값을 구할 수 있습니다.

 

글로는 이해가 어려우니

이미지로 설명하겠습니다.

위 그림과 같이

전체 범위 range 배열을 생성하고,

시작점과 끝점의 인덱스를 지정할

start, end 를 생성했습니다.

 

그리고 range배열에서

각 좌표들의 시작점 인덱스에 +1,

끝점+1 인덱스에 -1 을 할당해줍니다.

(이 부분은 이 알고리즘을 공부할 정도면,

스스로 할 수 있다고 판단하고 안그렸습니다.

사실 시간이 없습니다 ㅠㅠ)

 

 

그리고 다음 그림으로 넘어갑니다.

좌표가 표기된 range 배열을

for문을 이용해서 다시 한번 훑게 되면,

겹치는 만큼 숫자의 카운트가 올라갑니다.

 

이제 원하는 값을 얻었으니

출력하면 끝입니다.

 

저는 실력이 미천해서

아주 간단하게만 imos 법을 훑어봤고,

 

구글에 검색하시면

이걸 활용한 더 복잡한 알고리즘을

설명하고 있는 글들이 또 있습니다.

 

더 심화학습을 원하신다면 찾아보시길 권해드립니다.

 

 

 

ps. 아, 그리고 이전 글에도 적긴 했는데,

참고로 전 이 알고리즘으로 문제를 풀진 못했습니다.

 

제가 풀려던 문제는 겹치는 좌표를 구하는 게 아니라,

겹치는 부분의 길이를 구하는 문제였는데,

그림에 보다시피, 3~4 구간은 겹치지 않음에도

 

3에도 2 카운트,

4에도 2 카운트가 돼있어서,

 

만약 2 이상인 좌표의 길이를 구하라고

코드를 짰다면, 3이라는 길이가 나오고,

겹친 길이는 2 이니, 틀린게 됩니다.

 

그래서 저 상태에서 계속 빙빙 돌다가,

결국 선생님의 도움을 받아서,

조금 다른 알고리즘을 적용해서 풀었습니다.