자료구조에서 사이클 찾아내기

Tortoise racing hare


Linked list가 있다고 합시다. 이 연결 목록에 사이클이 있으면 무한루프를 돌게 되므로, 반복문을 돌기 전에 사이클이 있는지 검사하고 싶습니다. 어떻게 하면 될까요?

루프를 돌면서 한번 나온 노드들은 그 신분(C++의 경우 노드의 주소값이 편리하겠죠)을 기록해두었다가, 다 돌기 전 같은 놈이 또 나오면 사이클이 있다고 판단할 수 있겠죠. 한번 나온 놈들을 기록하는 자료구조로는 해쉬테이블이나 이진트리를 쓰면 될겁니다.

그러나 목록에 있는 아이템의 개수에 상관없이 단 두 개의 포인터만으로 사이클을 검출해내라 한다면 어떨까요? 다시 말해, 추가적인 저장소 오버헤드(위의 해쉬테이블이나 이진트리 같은)를 없게하고 알아내라는 말입니다.

이미 알고 계셨던 분을 제외하고는 방법을 짜내기가 쉽지 않을 겁니다.



첫번째 힌트 보기




두번째 힌트 보기






그 차이는... 직선 경로에서는 속도가 다른 토끼와 거북이가 출발선 이외에서는 서로 만날 일이 다시 없지만, 원형 경로를 계속 달리는 경우에는 주기적으로 다시 만나게 된다는 것입니다. 이에 착안하여 나온 것이 Floyd의 알고리즘입니다. 하나씩 아이템을 살피는 거북이 iterator(혹은 포인터)와 하나씩 걸러서 아이템을 살피는 토끼 iterator를 사용합니다. 이를 개선한(이해하기는 좀 더 어렵지만) Brent의 알고리즘도 있군요. (해당 위키피디아 페이지에 알고리즘의 파이썬 코드와 자세한 설명이 나와 있으니 꼭 한번 읽어보세요.)

저장소 오버헤드에 대한 제약이 없다면, 굳이 이런 트릭을 써야 할 필요는 없습니다만, 사이클에 대한 토끼와 거북이의 통찰은 일반적인 패턴으로 익혀둘만 하다고 생각합니다. ^^




* 이 포스트는 blogkorea [블코채널 : 웹, 컴퓨터, it에 관련된 유용한 정보 및 소식] 에 링크 되어있습니다.
Trackback 0 Comment 7

top