floyd's cycle detection1 Floyd's Cycle detection algorithm with GoLang i.stack.imgur.com/TQoyH.png 서로 다른 속도로 이동하는 포인터를 다음과 같이 가정, 느린 포인터 이동 속도 = 1 빠른 포인터 이동 속도 = 2 각 포인터의 시작 지점을 다음과 같이 지정, 느린 포인터 시작 지점 = 0 빠른 포인터 시작 지점 = 1 그랬을 때, 두 포인터가 위의 그림과 같은 순환 경로를 진행 시 meeting-point 에서 만났을 때 다음과 같음을 알 수 있음, 느린 포인터가 만나기 까지 이동한 거리 = x + y 빠른 포인터가 만나기 까지 이동한 거리 = x + y + z + y = x + 2y + z 빠른 포인터는 느린 포인터보다 두 배 빠른 속도로 이동 했기 때문에, 느린 포인터가 이동한 거리의 두 배가 곧 빠른 포인터가 이동한 거리가 됨. 이를 수식으로 표.. 2020. 10. 13. 이전 1 다음
