[알고리즘] 링크드 리스트 순환 탐지 알고리즘 증명 (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 Lfast 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