플로이드 순환 검출 계산기 (토끼와 거북)

간격이 매 걸음 정확히 1씩 줄어들게 하기 위해서입니다. 둘이 고리 안에 들어온 뒤 간격이 1씩 줄면 0을 건너뛸 수 없어 반드시 같은 자리가 됩니다. 세 칸씩 보내면 간격이 2씩 줄어 이 성질이 깨지고, 고리 길이가 짝수일 때 영영 못 만날 수 있습니다.

만난 시점에 거북이 걸은 수 t가 고리 길이 λ의 배수이기 때문입니다. 토끼는 2t를 걸었고 둘이 같은 자리에 있으므로 두 걸음 수의 차 t도 고리를 정수 바퀴 돈 것이 됩니다. 이제 한 포인터를 출발점으로 되돌려 둘을 한 칸씩 보내면, 출발점 쪽은 μ걸음에 진입점에 닿고 만난 자리 쪽은 t + μ를 걸어 역시 진입점에 섭니다. 그래서 처음 다시 만나는 자리가 진입점입니다.

더 간단하지만 메모리를 훨씬 많이 씁니다. 첫 중복이 곧 답이라 코드는 짧지만 꼬리와 고리를 합친 만큼(μ+λ) 적어 둘 자리가 필요합니다. 플로이드는 포인터 두 개만 쓰므로 입력이 아무리 커도 메모리가 일정합니다. 걸음 수는 몇 배 더 걷는 대신 메모리를 아끼는 맞바꿈입니다.

상태가 유한하고 다음 자리가 하나로 정해지면 고리가 없을 수 없습니다. 갈 곳이 유한한데 끝없이 가야 하니 언젠가 왔던 자리를 다시 밟게 되기 때문입니다(비둘기집 원리). 그래서 이 계산기에 「고리 없음」이라는 답은 나오지 않으며, 최악이라도 μ + λ가 상태 수를 넘지 않습니다.

μ는 출발점에서 고리에 들어가기까지의 걸음 수(꼬리 길이)이고, λ는 고리를 한 바퀴 도는 걸음 수(고리 길이)입니다. 수열을 그림으로 그리면 꼬리 뒤에 고리가 달린 그리스 문자 ρ 모양이 되는데, 순환 마디를 「로(rho)」라 부르는 것이 여기서 왔습니다.

연결 리스트에 사이클이 있는지 판정하는 문제로 가장 널리 알려져 있습니다. 그 밖에 난수 생성기의 주기를 재거나, 폴라드 로 소인수분해처럼 「같은 값이 다시 나오는 순간」을 메모리 없이 잡아야 하는 곳에 쓰입니다. 값을 전부 적어 둘 수 없을 만큼 상태가 클 때 값어치가 큽니다.

전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.