NeuroWhAI의 잡블로그

이 알고리즘은 우연히 알게되었다. 구현은 참으로 간단한데 이게 왜 되는지 이해가 안돼서 한참을 삽질했다. 정리할 겸 글을 적어본다. 일단 알고리즘의 목적은 유향 그래프든 연결 리스트든 그 속에 순환이 존재하는지, 존재한다면 그 시작 지점은 어딘지 찾는 것이다. 1. 먼저 시작 노드를 가리키는 포인터 2개를 준비한다. 2. 노드의 간선을 따라 포인터를 이동시킬 것인데 하나는 1칸씩, 다른 하나는 2칸씩 옮긴다. 3. 순환이 없다면 두 포인터가 만나는 일은 없겠지만 순환이 존재하면 결국 만나게 된다. 4. 이때 느린 포인터를 다시 시작 노드로 옮기고 이번엔 둘 다 1칸씩 이동시킨다. 5. 그럼 또 결국 어떤 지점에서 만나게 되는데 놀랍게도 여기가 순환이 시작되는 곳이다. 이 방법으로 순환을 찾을 수 있다는 ..