플로이드의 토끼와 거북이 알고리즘(Floyd's hare and tortoise) 증명

토끼와 거북이 알고리즘은 선형으로 이루어졌거나 링크드리스트 자료구조에서 Cycle 이 존재하는지 찾아내고 그 Cycle 의 시작지점을 알아내는데 유용하다

이 알고리즘을 요약하면 

거북이는 한 번에 한 칸을 가고 토끼는 한 번에 두 칸을 보낼때 
만약 Cycle 이 존재한다면 둘은 결국 만난다. 
Cycle 이 존재하지않는다면 토끼가 null 이 된다.

이 알고리즘을 수학적으로 증명해보자

Cycle 이 존재하지 않는 경우 토끼가 리스트의 끝으로 가서 결국 null 을 가리키게되는 건  자명하므로 생략한다.

 

토끼가 두 칸을 가고 거북이가 한 칸을 갈 때 둘은 무조건 만난다.

용어를 정의하자

토끼가 움직이는 거리를 h(hare 의 줄임말) 거북이가 움직이는 거리를 t(tortoise 의 줄임말) 라고 하자 그러면

h = 2t

이다. 토끼가 거북이의 두 배를 간다.

우리가 증명해야 하는 건 

(t+d) mod m = t

이다. 여기서 d 는 임의의 거리를 의미하고 m 은 Cycle 의 길이를 의미한다. 수식을 그대로 풀어보면 거북이가 간 거리 t 로부터 d 만큼의 거리를 더 간 토끼의 위치를 Cycle 의 길이 m 으로 modular 연산했을 때 거북이의 값과 똑같은 값이 나오면 둘은 같은 위치라는 의미다.

 

즉, Cycle 이 존재할 때 둘이 아직 만나지 않았다면 거북이가 위치한 t 로부터 토끼는 얼마간 떨어져있다. 얼마인지는 모른다. 하지만 토끼는 거북이의 2배를 가기 때문에 토끼가 간 거리는 (t + d) 가 된다. 역시 d 가 얼마인지는 모른다. 만약 여기서 Cycle 의 길이만큼 modular 연산을 해줬을 때 t 와 같다면 토끼와 거북이는 한 자리에 있다. 

h = 2t 이기 때문에 h/2 = t 이다.

위 공식을 대입해보면

((h/2) + d) mod m = h/2
= (h + 2d) mod 2m = h
= (h + 2d) = ( 2m * K ) + h, k 는 어떤 정수다.
= 2d = 2m * K
= d = m * K

결국 d = m * K 이다

K 는 어떤 정수로서, 토끼가 얼마나 많이 Cycle 을 돌았는지 나타낸다. 

m 은 Cycle 의 전체 길이를 의미한다. 즉 d 는 Cycle 을 몇바퀴 돌았는지 나타낸다

아까 봤던 이 공식을 기억하는가?

(t+d) mod m = t

여기서 d 는 그저 Cycle 을 몇 번 돌았는지 나타낼 뿐이므로 '위치'의 관점에서 무시할 수 있다. Cycle 을 100만번 돌아도 결국 같은 자리로 돌아오기 때문이다. 

따라서 토끼는 무조건 거북이와 만난다.

 

토끼와 거북이가 만났을 때 거북이만 다시 시작지점으로 옮긴 후 토끼와 거북이 모두 한 칸씩 이동시키면 둘이 만나는 지점이 바로 Cycle 의 시작지점이다.

용어를 정의하자

a: 시작지점에서 Cycle 시작지점까지의 거리

m: Cycle 의 길이

b: Cycle 안에서 토끼와 거북이가 만날 때 까지의 거리, 즉 Cycle 시작지점으로부터 토끼와 거북이가 만나는 지점까지의 거리

 

토끼와 거북이가 만난다면 토끼가 움직인 거리는 a + b + j*m 이다. j 는 어떤 정수이다.

거북이가 움직인 거리는 a + b 이다.

 

토끼가 거북이보다 두 배 빠르게 움직이기 때문에

2(a + b) = a + b + jm
= 2a + 2b = a + b + jm
= a + b = jm
= a = jm - b

결국
a = jm - b 가 된다.

이걸 더 풀어보면
a = m - b + (j-1)m
a = m - b + km
m - b = km - a

가 된다.

근데 m 은 Cycle 전체의 길이이기 때문에 '위치'의 관점에선 무시해도 상관없는 값이다.

결과 b 와 a 는 '같은 거리에 있다.'고 말할 수 있다. 따라서 시작지점으로 옮긴 거북이와 Cycle 에 남아있는 토끼를 한칸씩 이동시키면 둘이 만나는 지점이 Cycle 의 시작지점이다.