Floyd의 tortoise and hare로 사이클을 어떻게 탐지하나요?

Question

Accepted Answer

**Floyd의 사이클 탐지**는 서로 다른 속도로 움직이는 두 포인터를 사용하여 시퀀스(연결 리스트 같은)에서 루프를 찾습니다. 사이클이 존재하면 빠른 포인터가 결국 한 바퀴 앞서 느린 포인터와 만납니다. **O(1)** 추가 공간을 사용합니다.

## 개념

**느린(slow)** 포인터는 한 걸음, **빠른(fast)** 포인터는 두 걸음 움직입니다. 사이클 안에서는 간격이 매 걸음 하나씩 줄어들므로 반드시 충돌합니다. 사이클이 없으면 빠른 포인터가 끝에 도달합니다.

## 예시

```python
def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next            # +1 걸음
        fast = fast.next.next       # +2 걸음
        if slow is fast:            # 포인터가 만남 -> 사이클
            return True
    return False                    # fast가 끝에 도달 -> 사이클 없음
```

## 복잡도

- **시간:** O(n). **공간:** O(1).

해시 셋 방식도 동작하지만 O(n) 공간이 듭니다. Floyd의 방식은 상수 공간을 사용합니다.

## 언제 사용하나 / 함정

**연결 리스트 루프 탐지**, 사이클의 시작점 찾기, 함수형 그래프(각 노드가 후속 노드 하나를 가짐)의 사이클 탐지에 사용하세요. 항상 `fast.next`를 가드하여 null 역참조를 피하세요. 일반 그래프에서는 대신 재귀 스택을 사용한 DFS를 쓰세요.

## 왜 중요한가

사이클 탐지는 안전한 순회에 필수적입니다 — 탐지되지 않은 루프는 무한 반복을 의미합니다.

Floyd의 알고리즘은 영리한 불변식으로 O(n) 공간 문제를 O(1) 공간에 푸는 아름다운 예시입니다.

연결 리스트 면접과 상태 기계 및 수열에서의 무한 루프 탐지에 등장합니다.