Floyd's Cycle Starting Point 설명 및 수학적 증명 (feat. 연결 리스트)

개요

연결리스트(Linked List)는 대표적인 선형 자료구조 중 하나로 동적으로 새로운 노드를 삽입하거나 삭제하기도 간편하며 연결 구조를 통해 물리 메모리를 연속적으로 사용하지 않아도 되기에 관리도 쉽다.

 

Floyd's cycle 은 연결리스트 자료형에서 사이클을 포함여부를 확인하는 것과 동시에, 사이클의 시작점을 확인할 수 있다. (시간복잡도 O(N), 공간복잡도 = O(1)를 가진다.) 

 

1. 사이클 존재여부 판단

1-1. 시작점에서 Slow Pointer와 Fast Pointer를 정의하자.

1-2. 여기서, Slow Pointer는 한 노드 단위, Fast Pointer는 2 노드 단위로 움직이도록 한다.

1-3. 서로 간 속도가 다르기에, 만약 사이클이 존재하지 않는다면 노드 구간에서 Slow Pointer는 절대로 Fast Pointer를 만날 수 없다.

1-4. 사이클이 존재한다면 Slow Pointer와 Fast Pointer의 접점은 반드시 존재한다. (아래 Step 2에서 증명 예정)

 

즉, Fast Pointer와 Slow Pointer와의 접점이 확인 된다면 사이클은 존재한다고 말할 수 있다.

 

2. 사이클 시작점 판단

만약 연결리스트 내 사이클이 존재할 시 사이클의 시작점은 다음의 순서대로 판단한다.

 

2-1. 사이클이 존재하면 Slow Pointer와 Fast Pointer의 접점은 반드시 존재한다.

2-2. Slow Pointer와 Fast Pointer 접점에서 Slow Pointer는 Starting Point로 보낸다.

2-3. Slow Pointer와 Faster Point의 속도를 1 노드 단위로 이동시키며, 이 둘의 접점은 사이클 시작점이다.

 

3. 수학적 증명

 

이에 대해서 수학적으로 증명을 통해 이해를 더해보자.

 

아래 2가지 내용에 대하여 수학적으로 증명할 것이다.

첫째, 사이클이 존재할 시 Meeting Point는 반드시 존재한다.
둘째, Starting Point ~ Cycle Point 거리 = Meeting Point ~ Cycle Point 거리는 같다.
(※ 아래 참조한 링크를 참조하여 추가 증명하였으며, 혹시 오류 발견시 댓글로 남겨주세요.)

 

---

참조

https://abhisekbunty94.medium.com/why-does-floyds-cycle-detection-algorithm-work-59f61984dc3e#67a7