5. 플로이드의 순환 찾기 알고리즘과 정수 이론 알고리즘

1. 개요

 문제는 이렇다. 어떤 리스트가 있다. 그 리스트의 구조는 모른다. 이 때, 이 리스트의 구조가 순환 형태인지 아닌지 어떻게

알 수 있을까? 

 이 문제를 O(n)에 풀어내는 알고리즘이 플로이드의 순환 찾기 알고리즘이다.

  

플로이드의 순환 찾기 알고리즘을 단순히 표현하면 이렇다. 만약

 

 (출처) https://nol2soft.wordpress.com/2013/07/13/linked-list-cycle-detection-explanation

 이런 형태의 순환 리스트가 있을 때, 토끼와 거북이가 시작점에서 출발한다. 토끼는 거북의 속도보다 2배 더 빠르다. 

토끼가 먼저 출발한다. 당연히 토끼보다 느린 거북이는 평생 토끼를 잡을 수 없다. 그렇지만 만약 둘이 만나게 되면

이 리스트는 순환 구조를 가졌다고 판명된다. 

 여기까진 굳이 플로이드의 순환 찾기 알고리즘이라는 거창한 이름없이 그냥 당연한 알고리즘이다. 하지만 이제부터 

엄청난 사실이 등장한다. 바로 이 순환의 시작점을 어떻게 찾을까? 라는 문제가 나온다면 어떻게 풀어야할까? 

2. 풀이

 즉, 위의 그림에서 m의 길이를 어떻게 찾아낼까? m의 값을 모른다. n의 값도 모른다. 

 이 문제는 정수 이론의 핵심이다. ( 나는 잘모른다. ) 하지만 이론은 일단 제쳐두고 아주 간단한 사실이있다.

 답은 이렇다. 

 토끼는 토끼와 거북이가 만난 자리인 k에서 출발하고 거북이는 시작점에서 출발한다. 

 이 때, 둘이 만나는 최초의 자리가 바로 순환의 시작점이다.

 너무 놀랍다. 그리고 한동안 이게 왜 이런지 알 수가 없었다. 하지만 우리가 색깔을 판단할 때 파랑은 파랑이지

파랑색을 이루는 가시광선이 어떤지 알 필요는 없다. 마찬가지로 나도 이해없이 이 사실만을 알아두고 훗날 필요한

일이 있을 때 써먹어 보고 싶었지만 너무 궁금해서 증명을 찾아냈다.

 m = 순환까지의 거리 (찾아야 할 값)

 n = 순환 루프의 길이

 k = 순환 시작점에서 토끼와 거북이가 만난 자리까지의 거리

 자, 여기서 위의 이론을 증명하려면 k와 시작점에서 한 칸씩 이동했을 때 둘이 만나는 장소가 순환의 시작점이다.

=> m + k (시작점에서 만난 자리까지의 거리) + n - k (루프 길이에서 k값을 뺀 나머지) 이 m이라면 성립된다.

=> ( m + k ) + ( n - k ) = m 에서 n - k가 m과 같냐는 것을 보이고 싶기 때문에 n - k = m을 대입한다.

=> ( m + k ) + m = m

=> m + k = 0

=> m = -k

하지만 거리를 구하는 것이기 때문에 절대값을 붙이면 m == k는 동등하다.

3. 결론

 일단 역시 스승님은 위대하다. 이런 사실을 알게 해주셔서. 하지만 솔직히 이 이론을 언제 써먹어서 코드로 작성

할 날이 올지 모른다. 아마 평생 안올지도 모른다. 하지만 굳이 이 글을 쓴 이유는 이 알고리즘을 이해하려고 노력

하면서 처음으로 수학적 공식을 대입하며 증명을 해보려 노력하였다. 한 번 해봤으니 앞으로도 수학적 이론이 겹친

문제에서 이렇게 풀이할 수 있다는 접근법을 알게되었다. 이와같은 방법으로 계속 연습하여 수학 코딩에서 역량을

발전시키자!! 할 수있다! 쫄지말자!