에듀테크 프로젝트 대시보드
플로이드 순환 탐지 (토끼와 거북이)
연결 리스트에 고리(사이클)가 있는지, 있다면 어디서 시작하는지를 추가 메모리 없이 알아내는 방법. 느린 포인터(거북이 🐢)는 한 칸, 빠른 포인터(토끼 🐇)는 두 칸씩 움직인다. 고리가 있으면 토끼가 반드시 거북이를 한 바퀴 안에서 따라잡는다.
set에 넣고 다시 나오면 사이클"이라고 하면 간단하지만 노드 수만큼 메모리(O(n))를 쓴다. 플로이드 방법은 포인터 딱 2개, 즉 O(1) 메모리로 끝낸다. 리스트가 10억 개여도 변수 두 개뿐.
아래는 꼬리 μ칸 + 고리 λ칸 짜리 리스트다. 「시작」을 누르면 거북이는 1칸, 토끼는 2칸씩 전진한다. 1단계에서 둘이 만나는 지점을 찾고, 2단계에서 한 포인터를 머리로 되돌려 같은 속도로 걸어 고리의 시작점을 찾는다.
두 포인터가 모두 고리 안에 들어온 뒤를 생각하자. 고리 둘레는 λ. 매 스텝마다 토끼는 거북이보다 정확히 1칸 더 다가간다(2 − 1 = 1). 즉 둘 사이 거리가 매 스텝 1씩 줄어든다. 거리는 0 ~ λ−1 중 하나이므로, 늦어도 λ 스텝 안에 거리가 0 = 같은 노드에 선다. 고리가 없으면 토끼가 먼저 리스트 끝(null)에 도달 → "사이클 없음".
머리에서 고리 시작까지 거리를 μ, 고리 둘레를 λ라 하자. 거북이가 k칸 갔을 때 처음 만났다면 토끼는 2k칸 갔고, 둘 다 고리 위 같은 점에 있으므로 두 거리의 차 2k − k = k는 λ의 배수다.
따라서 만난 지점에서 μ칸 더 가면 고리 시작점이다. 그런데 머리에서도 시작점까지 정확히 μ칸이다! 그래서:
ptr)를 머리로 옮긴다. 다른 하나는 만난 지점에 둔다.def detect_cycle(head): slow = fast = head # --- 1단계: 만남 지점 찾기 --- while fast and fast.next: slow = slow.next # 1칸 fast = fast.next.next # 2칸 if slow is fast: break # 사이클 발견 else: return None # fast가 null 도달 → 사이클 없음 # --- 2단계: 고리 시작점 찾기 --- ptr = head while ptr is not slow: ptr = ptr.next slow = slow.next return ptr # 고리 시작 노드 # --- (보너스) 고리 길이 λ --- # 시작점에서 한 바퀴 돌아 제자리로 오는 횟수를 세면 된다
else는 break 없이 루프가 끝났을 때 실행된다. 위 코드에서 fast가 null에 닿아 자연 종료되면 "사이클 없음"으로 None을 돌려준다.
| 방법 | 시간 | 메모리 | 비고 |
|---|---|---|---|
방문 노드를 set에 저장 | O(n) | O(n) | 가장 직관적. 큰 리스트에서 메모리 부담 |
| 노드에 "방문" 플래그 기록 | O(n) | O(1) | 원본 데이터를 훼손. 불변 구조엔 불가 |
| 토끼와 거북이 (플로이드) | O(n) | O(1) | 포인터 2개. 시작점·길이까지 계산 가능 |
| 브렌트(Brent) 알고리즘 | O(n) | O(1) | 비교 횟수가 더 적은 개선판 |
연결 리스트 버그 탐지 — 포인터를 잘못 이어 붙여 생긴 무한 루프를 찾는다. LeetCode Linked List Cycle 계열 문제의 정석.
난수열의 주기 찾기 — xₙ₊₁ = f(xₙ) 형태 의사난수 생성기는 유한 상태라 언젠가 반복된다. 그 주기(period)를 메모리 없이 측정.
폴라드 로(Pollard's rho) 소인수분해 — 큰 수를 나누는 인수를 찾을 때, 수열 x² + 1 mod n 의 사이클을 토끼·거북이로 감지한다. 이름의 "ρ" 모양이 바로 이 그림.
"중복된 수 찾기" — 1..n 범위 배열에서 값을 다음 인덱스로 해석하면 리스트가 되고, 중복 값이 곧 고리 시작점이 된다. (LeetCode 287)