토끼와 거북이 알고리즘

출처 : http://minjang.egloos.com/1687021

영어 질문 하나. 우리가 잘 아는 이솝 우화, '토끼와 거북이'를 영어로 하면은? 학교에서 거북이는 Turtle로 배웠고 토끼는 Rabbit으로 배웠으니...

Rabbit and Turtle ?

안타깝게도 이것은 정답이 아니다. 토끼와 거북이는 영어로

Tortoise and Hare

로 쓴다. 내가 Rabbit and Turtle라는 말을 쓰자 인도친구가 웃으면서 Tortoise and Hare로 고쳐주더라.

그런데 정작 하고 싶은 이야기는...

Tortoise and Hare, 즉 토끼와 거북이 알고리즘이라는 것이 있다. 주어진 리스트에 싸이클이 있는지 없는지를, 보다 일반적으로 표현하면 주어진 함수에서 싸이클이 있는지 없는지를 알려주는 알고리즘이다. 이 알고리즘을 고안한 사람은 Floyd라는 사람이다. 알고리즘 책에서 본, 그 짧은 코드에도 불구 오묘한 기능을 하는 All Shortest Path 알고리즘을 만든 그 Floyd이다.

그림을 그려서 다시 이 문제를 설명하면,

링크드 리스트에서 O(n) 시간과 O(1) 저장 공간을 이용해서 싸이클이 있는지 없는지를 알아내어라.

만약 시간과 저장 공간의 제약이 없다면, 노드마다 방문 되었는지 기억하는 변수를 하나 두고 돌아다니면 될 것이다. 그러나 문제에서는 O(1)의 공간, 즉 이런 추가적인 변수를 둘 수 없다. 그렇다면 일반적인 방법으로는 풀기가 어렵다. 여기서 아주 기발하게 토끼와 거북이가 등장해서 싸이클 유무를 판단할 수 있다.

1. 거북이는 리스트를 한 번에 한 노드씩 앞으로 나아간다.
2. 반면에 토끼는 두 걸음씩 움직인다.
3. 이런 과정을 계속 반복한다.

만약 리스트에 싸이클이 있다면? 그렇다면 이 둘은 언젠가 만나게 될 것이다.

그림을 그려서 확인해보자. (PowerPoint 2007 만세~)

이렇게 보다시피 언젠가는 만나게 됨을 직관적으로 알 수 있다. Wiki에는 리스트가 아닌 함수에서 싸이클 찾는 알고리즘을 Python으로 기술하고 있다. (리스트일 경우에는 단순히 함수 f를 다음 노드를 반환해주는 것으로 만들면 될 것이다.)

def floyd(f, x0):

    # The main phase of the algorithm, finding a repetition x_nu = x_2nu

    # The hare moves twice as quickly as the tortoise

    tortoise, hare = f(x0), f(f(x0))

    while tortoise != hare:

        tortoise = f(tortoise)

        hare = f(f(hare))

Floyd의 논문에는 단순히 싸이클의 존재 유무를 떠나 모든 싸이클 (보다 엄밀하게는 simple cycle)을 다 찾고 나열할 수 있는 알고리즘이 나와있다 (Fig. 5~8). 그러나 정확히 위의 pseudo code처럼 토끼와 거북이를 명시한 알고리즘은 아니다.

Floyd는 이런 알고리즘을 Back-tracking 알고리즘과 구분하여 Nondeterministic 알고리즘이라고 부른다. 흔히 우리가 알고 있는 Nondeterministic Turing Machine의 행동과 비슷하다. NTM에서는 다음 스텝으로 갈 때, 일반적인 Deterministic TM처럼 한 곳으로만 가는 것이 아니라 (확률에 의존적이지가 않고) 여러 군데로 가는 것을 허용한다. Floyd가 제안한 Nondeterministic 알고리즘은 이와 유사하게 multivalued function (아래 참고)을 도입하여 비결정성을 구현하고 있다. 그러나 결국 컴퓨터로 돌리기 위해서는 deterministic 해야 하니 실제 모든 루프(=싸이클)를 찾는 알고리즘을 보면 (컴파일러 최적화에서 쓰이는 것) Floyd가 제시한 알고리즘과 매우 유사하지만 모든 스텝이 결정적으로 이루어져있다. 더 이상 쓰려니 머리가 아파서 그만...

암튼 결론은 리스트에서 싸이클을 찾고 싶을 때 토끼와 거북이를 이용하라는 것.

@ Multivalued function: 간단하게 말하면, 함수는 x원소에 대응되는 y 원소가 오직 하나 뿐임에 비해 이 multivalued function은 f(x)가 여러 개의 y 값을 가지고 있음. 즉, 일반적인 함수의 정의에는 위배됨.

@ 그냥 관심있으면 보시라고 Floyd의 논문을 직접 다운 받아 여기에 올렸는데 설마 잡아가지는 않겠지...