Floyd's tortoise and hare algorithm

이 글은 주니온TV 아무거나연구소 및 다른 글을 참고하여 작성된 글입니다.

 

 

토끼와 거북이 알고리즘

- 서로 다른 속도로 움직이는 두 개의 포인터를 이용해서 O(n)의 시간 복잡도, O(1)의 공간 복잡도로 cycle detection problem을 해결하는 알고리즘 (https://en.wikipedia.org/wiki/Cycle_detection)이다. 주어진 링크드 리스트에 사이클 존재 유무를 확인할 수 있는 방법이다.

 

 

 

1. 토끼와 거북이는 같은 장소에서 출발한다.

2. 거북이가 한 칸을 이동할 동안 토끼는 두 칸을 이동한다.

3. 만약 연결 리스트 내에 사이클이 없다면 토끼와 거북이는 이동 중에 Null 노드를 만날 것이다.(사이클 없음)

4. 만약 연결 리스트 내에 사이클이 있다면 토끼와 거북이가 언젠가 반드시 만날 것 이다.(사이클이 존재함)

대충 무슨 말인지 알 것 같다. 두 포인터를 활용해 각각 다른 속도로 이동하면서 언젠가 둘이 만난다면 사이클이 존재하는 것이고, 그렇지 않다면 사이클이 존재하지 않는 것이다. 중학교 때 체육 수행평가로 진행했던 오래 달리기가 기억난다. 이를 예로 들어본다. 같은 출발 지점에서 두 선수가 동시에 출발한다. 속도가 느린 A학생은 이제 반바퀴를 돌았다. 하지만 육상 선수였던 B학생은 빠르게 치고나가서 1바퀴를 다 돌고 다시 A학생을 마주했다. 이런 결과가 나오려면 운동장은 사이클이 존재해야 한다. 존재하지 않았다면 B학생은 교문 밖(?)으로 나갔을 지도....(그대로 땡땡이?)

 

 

토끼와 거북이 알고리즘 문제를 연습할 수 있는 문제이다.

LeetCode 141. Linked List Cycle

Linked List Cycle - LeetCode

 

 

 

동작 과정

1. 토끼와 거북이는 출발 노드에 같이 선다.

2. 토끼나 거북이가 종점 노드를 만나지 않으면 다음을 반복한다.

    2-1. 토끼는 두 칸을 전진한다. (중간에 종점 노드를 만나면 사이클이 없다고 리턴한다.)

    2-2. 거북이는 한 칸을 전진한다.

    2-3. 토끼와 거북이가 같은 노드에 위치했으면 사이클이 있다고 리턴한다.

3. 토끼나 거북이가 종점 노드를 만났으므로 사이클이 없다고 리턴한다.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        tortoise = hare = head
        while tortoise != None and hare != None :
            if hare.next == None :
                return False
            hare = hare.next.next
            tortoise = tortoise.next
            if hare == tortoise :
                return True
        return False

 

 

 

그렇다면 사이클이 시작하는 노드는 어떻게 구할 수 있을까?

1. 토끼와 거북이는 출발 노드에 같이 선다.

2. 토끼나 거북이가 종점 노드를 만나지 않으면 다음을 반복한다.

    2-1. 토끼는 두 칸을 전진한다. (중간에 종점 노드를 만나면 사이클이 없다고 리턴한다. null을 리턴한다.)

    2-2. 거북이는 한 칸을 전진한다.

    2-3. 토끼와 거북이가 같은 노드에 위치했으면 사이클이 있다고 리턴한다.  

           2-3-1. 토끼를 처음 위치로 보낸다.

           2-3-2. 토끼와 거북이가 만날 때까지 둘 다 한 칸씩 이동한다.

           2-3-3. 토끼와 거북이가 만난 위치의 노드(사이클 시작 노드)를 리턴한다.

3. 토끼나 거북이가 종점 노드를 만났으므로 사이클이 없다고 리턴한다.  null을 리턴한다.

 

왜 이렇게 되는지 자세하게 모르겠다. 그래서 직접 짜봤다.

출발점부터 사이클이 시작하는 노드(포함)까지가 홀수인 경우 / 사이클이 시작하는 노드포함 내부가 홀수인 경우 

출발점부터 사이클이 시작하는 노드(포함)까지가 홀수인 경우 / 사이클이 시작하는 노드포함 내부가 짝수인 경우 

출발점부터 사이클이 시작하는 노드(포함)까지가 짝수인 경우 / 사이클이 시작하는 노드포함 내부가 홀수인 경우 

출발점부터 사이클이 시작하는 노드(포함)까지가 짝수인 경우 / 사이클이 시작하는 노드포함 내부가 짝수인 경우 

 

 

 

모두 일치하였다. 좀 신기하면서도 이런 알고리즘도 모르는 것 보단 아는 게 좋을 것 같았다. 직접 짜보기 귀찮다면 https://visualgo.net/en/cyclefinding 을 활용해보길 바란다. 이해했다면 다음 문제를 풀어보자.

 

 

142. Linked List Cycle ||

Linked List Cycle II - LeetCode