[알고리즘] 링크드 리스트 순환 탐지 알고리즘 증명 (Floyd)

문제

Leetcode의 141번 문제를 보면 Tortoise and hare, 즉 토끼와 거북이 알고리즘으로 유명한 문제가 있다.

문제는 간단하게 말하자면 링크드리스트가 주어지고, 해당 링크드리스크가 싸이클이 있는지 없는지를 확인하는 문제가 주어진다.

• 입력 : 링크드 리스트의 head
• 출력 : 사이클이 있으면 true 없으면 false를 리턴

예를 들면 아래와 같이 사이클이 있는 링크드 리스트와 사이클이 없는 링크드 리스트가 있을텐데, 이 중에서 싸이클이 있는 케이스를 판별한다는 것이다.

사이클이 없는 링크드 리스트

사이클이 있는 링크드 리스트

위 알고리즘은 해쉬맵을 사용해서도 풀 수 있지만 가장 정석 방법은 Floyd가 제안한 cycle detection 알고리즘이다. 본 문제는 해당 알고리즘을 사용해 문제를 풀고 증명해본다. 어떻게 cycle을 탐지할 수 밖에 없는지에 대해 약간의 수학적 설명을 붙여 최대한 풀어서 설명하려고 한다.

 

자세한 문제는 https://leetcode.com/problems/linked-list-cycle/ 에서 읽어보길 바란다.

직관적 이해 그리고 문제의 답

일단 우선 문제 해답부터 공유하고, 왜 이게 해답이 되는지는 아래에서 증명하도록 하겠다.

해답을 읽기전에 독자는 먼저 생각해보고 문제를 풀어보는걸 추천한다.

 

그 후에 해답을 읽은뒤 왜 그런지 증명해보고 싶다면 아래 파트를 읽으면 되겠다.

 

플로이드의 알고리즘은 우선 Head를 가리키고 있는 다음 두 가지 종류의 포인터를 사용해 문제를 해결한다

한번 iterate할 때마다 i가 1씩 증가한다고 했을때, 아래와 같은 두 포인터를 두고 사이클을 탐지한다.

• slow pointer : i가 1 증가할 때마다 한 칸씩 next로 이동
• fast pointer : i가 1 증가할 때마다 두 칸씩 next로 이동

위 pointer를 설정해두고 만약 cycle이 있다면 i가 증가하다보면 결국 두 pointer가 만나는 경우가 생기게 된다.

 

직관적 이해

우선 수학적으로 설명해보기 전에 우선 직관적으로 이해를 해보자.

 

우선 cycle이 있는 케이스로 가정했을 때는 두 가지 사실을 알 수 있다.

(1) slow pointer가 loop에 들어갔을 때 fast pointer는 이미 loop에 들어간 상태다.

(2) fast pointer와 slow pointer 사이의 거리를 k라고 했을 때, 이 둘이 loop에 진입한 뒤부터는 한번 iterate할 때마다 (i가 1씩 증가할 때마다) 둘 사이의 거리는 k+1, k+2 … 이런식으로 계속 증가하게 될 것이고, 그러다가 loop의 길이인 n만큼 커지게되면 둘은 만나게 된다.

 

위 말이 잘 이해가 되지 않는다면 아래  loop을 기준으로 그린 그림을 보자.

 

위 그림에서 볼 수 있듯이, loop 속의 노드 개수가 6개일 때, i가 1씩 증가할때마다 slow pointer와 fast pointer간의 거리가 1씩 늘어나고 결국 6이 될때 거리가 0이 되는, 즉 결국 만나는걸 확인할 수 있다.

 

따라서, cycle이 있으면 둘은 만날 것이고 cycle이 없으면 fast pointer가 null이 될 것이다.

 

문제 답

class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """

        tortoise = head
        hare = head

        while tortoise != None and hare != None and hare.next != None:
            tortoise = tortoise.next
            hare = hare.next.next

            if tortoise == hare:
                return True

        return False

 

수학적 증명

증명을 하기 위해 예시를 하나 들어보겠다.

그림에서 보이는 것처럼 loop의 시작점에서 0부터 인덱스를 찍어주자.

다음과 같은 변수들을 정의해주자

• L : loop의 길이를 L

slow pointer

그리고 slow pointer가 loop의 시작점인 0번째 인덱스에 도달했을때 부터 i를 늘려며 iterate했을때의 index를 한번 계산해보자

iteration i		slow node의 링크드 리스트의 index
0		0
1		1
2		2
3		3
4		0
5		1
6		2
7		3
8		0
…		…

위 표에서 확인할 수 있듯이, i가 증가할때마다 slow pointer의 인덱스는 i mod L이 된다는 사실을 알 수 있다.

fast pointer

그리고 fast pointer가 loop의 시작점인 0번째 인덱스에 도달했을때 부터의 값을 한번 계산해보자

iteration i		fast node의 링크드 리스트의 index
0		0
1		2
2		0
3		2
4		0
5		2
6		0
7		2
8		0
…		…

위 표에서 보면 알 수 있듯이 i가 1증가할때마다 fast pointer의 인덱스는 (2*i) mod L임을 알 수 있다.

 

위 두가지 식에서 우리가 주의해야 할 것은, i 값은 두 node모두 loop의 시작점을 기준으로 계산했을 때 위 식이 나온다는 점이다.

 

앞서 우리가 한번 언급한적 있는데, slow pointer가 loop에 진입한 시점에는 fast pointer는 이미 loop에 들어가 있는 상태이기 때문에, 앞서 그린 그래프의 예제로 봤을 때 slow pointer가 loop에 진입한 시점의 링크드 리스트는 아래 그림과 같다.

 

위 그림에서 표현했듯, slow pointer가 loop에 도달한 시점에, fast pointer와 loop의 시작점으로부터의 거리는 d가 되고, 위 예시에서는 2다.

 

그리고 d의 범위를 표현하면 다음과 같다 0 ≤ d ≤ L-1 (L = length of loop)

 

문제에서는 slow pointer와 fast pointer가 모두 같은 시작점에서 출발했기 때문에, 이 케이스에서 fast pointer의 loop에서의 인덱스는 ((2*i) + d) mod L이 된다. ((2*i) mod L은 loop 시작점에서 움직였을때의 인덱스임)

 

따라서 우리는 위 예시에서 두 개의 식을 도출해낼 수 있다.

• slow pointer의 인덱스 : i mod L
• fast pointer의 인덱스 : ((2*i) + d) mod L

자 이제 우리는 slow pointer와 fast pointer가 i번 iterate되다가 결국에는 인덱스가 같아지는 (둘이 만나는 지점)이 있다라는 사실을 증명하기 위해 위 두 식을 활용할 것이다.

c를 L-d라고 간주하고, i=c로 값을 대입 후 두식을 한번 계산해보자.

• c = L-d이고, 0 ≤ d ≤ L-1 이기 때문에 1 ≤ c ≤ L이 된다.

 

(1) i iteration 후의 slow pointer의 인덱스는 i mod L이다.

따라서 i를 c값으로 대입하면 아래와 같이 전개된다.

i = i mod L

⇒ c mod L

⇒ c가 L일때 인덱스는 0,

⇒ c가 c<L 일때 인덱스는 c가 된다.

 

 

(2) i iteration 후의 fast pointer의 인덱스는 ((2*i) + d) mod L이다.

따라서 i를 c값으로 대입하면 아래와 같이 전개된다.

((2*i) + d) mod L

⇒ ((2*c) + d) mod L

⇒ (2c + d) mod L

⇒ (c + c + d) mod L

• c = L-d 로 가정했기 때문에 c 하나를 바꿔주면

⇒ (c + L - d + d) mod L

⇒ (c + L) mod L

⇒ c mod L

⇒ c가 L일때 인덱스는 0,

⇒ c가 c<L일때 인덱스는 c가 된다.

 

 

따라서 c일 때, slow pointer와 fast pointer가 모두 같은 인덱스에 있음을 알 수 있다.

 

 

 

본 글은 아래 글을 재구성 및 번역하여 작성한 글임을 알려드립니다.

https://www.geeksforgeeks.org/how-does-floyds-slow-and-fast-pointers-approach-work/

https://leetcode.com/problems/linked-list-cycle/solutions/44489/O(1)-Space-Solution/

https://dev.to/alisabaj/floyd-s-tortoise-and-hare-algorithm-finding-a-cycle-in-a-linked-list-39af