Algorithm Floyd's Tortoise and Hare Algorithm

알고리듬 Floyd's Tortoise and Hare Algorithm을 알아보겠습니다.

​
플로이드의 거북이와 토끼 알고리듬입니다. 이름이 너무 재미있지요. 순환을 찾는(Circle detect) 알고리듬 중 하나입니다.
토끼는 두 칸씩 뛰어가고 거북이는 한 칸씩 이동하면서 순환되는 부분을 찾는 알고리듬입니다.
​
이렇게 순환이 생기는 링크드 리스트가 있습니다.
여기서 플로이드 거북이와 토끼 알고리듬을 이용해서 순환이 발생하는지 확인하고, 그 시작 위치를 찾는 법을 알아봅시다.

거북이는 한 칸, 토끼는 두 칸씩 나아갑니다.

토끼와 거북이가 5에서 만났기 때문에 이 링크드 리스트는 순환하는 구조입니다.

여기서 재미있는 성질이 있습니다.

​

처음 순환이 발생하는 위치는 어떻게 구할까요? 우리가 보기에 3에서 순환이 발생하잖아요. 이것을 어떻게 찾냐하면 다음과 같이 찾습니다.

거북이를 원래 위치로 보내고, 거북이와 토끼를 한 칸씩 만날 때까지 움직이면 됩니다.

짜잔.

이것이 어떻게 가능한지 증명해 볼까요?

​

순환이 시작되는 점까지의 거리를 l

순환 시작점부터 거북이와 토끼가 만나는 점까지를 m

순환하는 전체 부분을 c라고 표기합니다.

거북이가 이동한 거리를 t라고 한다면,

t = l + c * x + m입니다.

토끼가 이동한 거리를 h라고 한다면,

h = l + c * y + m입니다.

​

토끼는 거북이보다 2 배 이동하니까

2t = h가 성립되어서

2(l + c * x + m) = l + c * y + m이 됩니다.

2l + 2 * c * x + 2m = l + c * y + m이 되고,

l과 m으로 정리하면,

l + m = (y - 2x) * c 가 됩니다.

y - 2x는 어떤 상수이므로 K로 대체합니다.

l + m = K * c

우리가 구하려는 l을 구해보면,

l = K * c - m이 됩니다.

​

K가 몇이든 결국 c - m이 됨으로

l = c - m이 되어, 순환이 시작되는 지점까지의 거리는 만난 지점에서부터 순환이 시작되는 거리와 같습니다.

​

​

​

파이썬 코드로 봅시다.

Node를 하나 만들고, 위의 그림처럼 1, 2, 3, 4, 5, 6이 연결된 상태로 만듭니다.

22 번째 줄과 23 번째 줄에 각각 거북이와 토끼를 넣습니다.

25 번째 줄에서 다음이 있으면 거북이에 넣습니다.

28 번째 줄에서 다음의 다음이 있으면 토끼에 넣습니다.

38 번째 줄에서 토끼와 거북이가 같은 위치에 있을 때까지 반복합니다.

아니면, 토끼나 거북이가 더 이상 갈 곳이 없으면 break를 합니다.

while 반복문을 빠져나온 다음 50 번째 줄에서 확인을 합니다.

이게 다음이 없어서 빠져나온 건지, 같은 위치에 있어서 빠져나온 건지 확인을 해봐야 하기 때문입니다.

같다면, 순환을 찾은 것이고 여기서 더 나아가 순환이 시작되는 지점을 찾아봅시다.

52 번째 줄에서 거북이를 다시 처음 위치로 보냅니다.

그리고 거북이와 토끼를 한 칸씩 움직여서 만나는 지점을 찾습니다.

끝.

카테고리: Algorithm