플로이드 순환 감지 알고리즘(Floyd Cycle Detection) – 연결 리스트에서 사이클 찾기

플로이드 순환 감지 알고리즘(Floyd Cycle Detection Algorithm)은 주어진 단일 연결 리스트(Singly Linked List) 안에 사이클(순환 구조)이 존재하는지 판별하는 대표적인 알고리즘 중 하나입니다. 흔히 거북이와 토끼 알고리즘(Tortoise and Hare)이라고도 불립니다.

이 알고리즘은 처음에 모두 헤드(head) 노드를 가리키는 두 개의 포인터를 사용합니다. 우화 속 이야기처럼 토끼(Hare)는 거북이(Tortoise)보다 항상 두 배 빠르게 움직입니다. 따라서 토끼가 경로의 끝에 도달했을 때, 거북이는 정확히 경로의 중간 지점에 도달하게 됩니다.

알고리즘 동작 원리

• 거북이(Tortoise)와 토끼(Hare) 포인터를 리스트의 헤드(head) 노드에서 초기화합니다.

• 토끼는 거북이보다 항상 두 배 빠른 속도로 이동합니다.

• 두 포인터를 이동시키면서, 토끼가 연결 리스트의 끝(end)에 도달하면 리스트에 루프가 없다는 것을 의미하므로 종료합니다.

• 그렇지 않다면 거북이와 토끼는 계속 앞으로 전진합니다.

• 만약 거북이와 토끼가 같은 노드에 위치하게 된다면, 리스트 내부에 사이클이 존재한다는 것이 확인된 것이므로 탐색을 종료합니다.

• 위 조건에 해당하지 않으면 2번 단계부터 다시 반복합니다.

알고리즘 의사코드(Pseudocode)

tortoise := headNode
hare := headNode
foreach:
    if hare == end
        return 'There is No Loop Found.'
    hare := hare.next
    if hare == end
        return 'No Loop Found'
    hare = hare.next
    tortoise = tortoise.next
    if hare == tortoise
        return 'Cycle Detected'