Floyd's tortoise and hare (cycle detection)

이미지 클릭시 동영상으로 이동

재미있는 유튜브 영상을 보게 되었다.
전체적인 영상의 재미는 애니메이션에서나 나올법한 웃긴 대사, 배경음악, 연출이다.

하지만 재미에 관한 이야기는 잠시 미뤄두고, 내용에 관해 이야기할 것이다.
영상의 내용은 이렇다. 주인공은 다음과 같은 알고리즘 문제를 풀게 된다.

Find Duplicate Number

Given an array nums containing $n + 1$ integers where each integer is between 1 and $n$ (inclusive), prove that at least one duplicate number must exist.
Assume that there is only one duplicate number, find the duplicate one.

Example 1:
Input : [1,3,4,2,2]
Output : 2

Example 2:
Input : [3,1,3,4,2]
Output : 3

Note: You must not modify the array ( assume the array is read only ).
You must use only constant, $O(1)$ extra space.
Your runtime complexity should be less than $O(n^2)$ .
There is only one duplicate number in the array, but it could be repeated more than once.

영상에서 문제를 한꺼번에 보여주는 장면이 없어서 받아적는데 조금 힘들었다.

아무튼 비둘기 집의 원리로 duplicate number는 당연하게 존재한다.

주인공은 처음에 이 문제를 이렇게 풀었다.
배열 속 원소들을 정렬하고, 정렬을 통해 인접한 중복된 숫자를 탐색한다.
파이썬의 list.sort() 내장함수가 정확하게 어떤 정렬 알고리즘을 사용하는지는 모르겠으나, 시간복잡도는 $O(nlogn)$ , 중복된 숫자 탐색은 선형탐색과 유사하며 $O(n)$ 의 시간복잡도를 가지게 되어 최종적으로 주인공은 $O(nlogn)$ 의 시간복잡도를 가진 풀이로 테스트를 하게 된다.
그리고 TIME EXEEDED. Too slow bitch라고 결과를 받게 된다. (..)
풀이를 아무리 봐도 $O(n^2)$ 보다 작은데, 그냥 연출인 것 같다.

두 번째 풀이로는 hashmap을 쓴다고 한다.
영상 풀이를 봐서는 hashmap을 사용하는 것 같지는 않은데 정확하게 어떤 코드를 썼는지는 모르겠다.
아무튼 MEMORY EXCEEDED라고 결과를 받게 된다.
아마 공간복잡도가 입력 크기에 영향을 받는 코드를 제출한 것 같다.

낙담하던 주인공 앞에 시니어 개발자 센빠이가 나타난다.
그러면서 Floyd’s tortoise and hare를 통해 이 문제를 해결할 수 있다고 한다.
결국 주인공은 문제를 해결하게 된다.

여기서 나는 저 플로이드의 토끼와 거북이라는 알고리즘에 대해 궁금해졌다.
이게 무엇이고, 어떻게 문제를 풀어주는지 찾아보게 되었다.

이미지 출처: http://1algo1week.warriorkitty.com/algorithm/2017/06/11/floyds-cycle-finding-algorithm.html

일단 이 알고리즘은 linked list 안에 cycle이 존재하는지 찾아주는 알고리즘이다.
알고리즘의 동작은 다음과 같다.

두 포인터 ( 토끼와 거북이 )는 linked list의 head를 가리키도록 한다.
이후 토끼 포인터는 한 번에 두 개의 다음 노드로 이동을 하고, 거북이 포인터는 한 번에 한 개의 개의 노드로 이동을 한다. 이것을 null에 도달하지 않는 한 계속 반복한다.
만약 이것이 circular linked list라면 언젠가는 만나게 된다.
만나게 되면 그 상태로 하나의 포인터를 다시 시작 위치로 옮긴다.
이후 두 개의 포인터를 한 번에 한 개의 노드로 이동을 반복한다.
이후 만나게 되는 노드를 반환하면 그 노드는 cycle이 시작하는 노드다.

어떻게 마지막에 만나는 노드는 cycle의 시작 노드일까?
이것의 증명은 인터넷에 검색해보면 나온다. 여기서 다루지는 않겠다.

# 결국 주인공이 Floyd's tortoise and hare로 풀은 풀이

def findDuplicate(nums):
  tortoise = nums[0]
  hare = nums[0]
  while True:
    tortoise = nums[tortoise]
    hare = nums[nums[hare]]
    if tortoise == hare:
      break

  ptr1 = nums[0]
  ptr2 = tortoise
  while ptr1 != ptr2:
    ptr1 = nums[ptr1]
    ptr2 = nums[ptr2]

  return ptr1

print(findDuplicate([3,1,3,4,2]))

이 알고리즘의 시간복잡도는 $O(n)$ 이며, 공간복잡도는 $O(1)$ 이라고 한다.
위에 문제를 푸는 데는 정말 효율적이다.

이런 알고리즘을 알고 있는 것도 신기한데, array를 linked list로, 그리고 중복된 숫자를 circular linked list의 cycle 시작지점이라고 생각을 확장하는 것까지는 정말 대단한 것 같다.

또한 글을 쓰면서 알게 된 것인데, 외국은 토끼와 거북이가 아니고 거북이와 토끼라고 하나 보다. 실제로 찾아보니 이솝우화의 토끼와 거북이도 “The Tortoise and the Hare”다. 그냥 뭐 그렇다.

Published 2020-03-05