[알고리즘] Floyd's tortoise and hare

플로이드의 토끼와 거북이라는 귀여운 이름을 지닌 알고리즘이다. 

다른 이름으론 플로이드의 순환 찾기 알고리즘으로 cycle detection에 사용된다. 

en.wikipedia.org/wiki/Cycle_detection

Cycle detection - Wikipedia

 

 

Cycle Detection

여기서 cycle detection이란 순차적인 함수의 연속된 값에서 cycle을 찾는 것이다.

순차적인 함수의 연속된 값들이란 

이런 것을 의미한다. 언젠간 Xi = Xj인 지점에 도달한다면 싸이클이 존재함을 의미하며 Xi부터 Xj-1까지의 값이 반복된다는 걸 알 수 있다.

cycle detection의 핵심은 f와 x0을 통해 i와 j를 찾는 것이다.

 

 

Floyd's tortoise and hare

cycle detection의 방법 중 하나! 바로 플로이드의 토끼와 거북이다.

두 개의 포인터를 사용하는 포인터 알고리즘으로 두 포인터가 서로 다른 속도로 이동하는 모습이 마치 이솝우화의 토끼와 거북이를 연상시켜 붙여진 이름이다. 

주로 linked list에서 cycle의 존재유무, cycle 길이, 시작점을 확인하기 위해 사용된다.

 

수도 코드를 살펴보자면

1. 거북이는 매번 한 칸씩, 토끼는 매번 두 칸씩 전진한다.

2. 사이클이 존재하지 않는다면 토끼는 마지막 노드에 도착한다.

3. 사이클이 존재한다면 토끼와 거북이는 사이클의 어딘가에서 반드시 만난다. 

3-1. 이 때 거북이를 처음 출발지로 돌려놓는다.

3-2. 이번엔 토끼와 거북이를 모두 1칸씩 움직였을 때 만나는 지점이 사이클의 시작지점이다.

3-3. 시작점을 모두 알았으니 토끼를 한칸씩 움직여서 사이클의 길이를 파악할 수 있다.

 

대충 이렇게 생겼다고 하면

동그란 싸이클 안에서 거북이와 토끼는 뛰다보면 만날 수 밖에 없다.

 

이 때 거북이를 출발지점으로 보내서 토끼랑 똑같이 달리게 한다면 사이클 시작지점에서 만난다는 건데 왜일까

 

 

 

 

 

 

야메 증명을 해보자

 

 

위 그림에서 토끼와 거북이가 만나는 시점은 저 별이다.

별을 기준으로 파란색이 토끼 경로, 초록색이 거북이 경로라면 토끼가 빠르니까 토끼는 한바퀴 돌아서 거북이를 만날 것이다.

 

여기서 토끼속도는 거북이 두배다. 즉 파란색 경로 길이가 초록색 경로 길이 *2 라는 의미다.

 

 

 

 

 

 

 

일자 막대기의 길이를 k 휘어진 막대기 길이를 l 원의 둘레를 d라 하자.

 

(k + l) *2 = (k + d)

 

k = d-l 이 된다. 정리하자면 토끼랑 거북이가 만난 위치부터 사이클 시작까지의 길이는 사이클 진입 직전의 길이와 동일하다는 의미이다.

 

그렇기 때문에 그 자리에서 1만큼 움직인 토끼와 출발지점으로 가는 거북이는 사이클 시작지점에서 만날 수 밖에 없다. 

 

node *find_loop(node *head)
{
	node *p1;
	node *p2;

	if (head == NULL)
		return (NULL);
	p1 = head; // 토끼
	p2 = head; //거북이
	while (p2->next != NULL && p2->next->next != NULL)
	{
		p1 = p1->next;
		p2 = p2->next->next;
		if (p1 == p2) //cycle이 있다면
		{
			p1 = head;//거북이를 head로 옮긴다.
			while (p1 != p2) //한 칸씩 움직여서
			{
				p1 = p1->next;
				p2 = p2->next;
			}
			return (p2); // 만나는 위치가 사이클 시작점
		}
	}
	return (NULL);
}