토끼와 거북이 알고리즘

If programming was an anime

(인생에서 본 “프로그래밍” 동영상 중 가장 웃겨요 ㅋㅌㅋㅋㅋ)

토끼와 거북이 알고리즘

오늘은 토끼와 거북이 알고리즘으로 풀 수 있는 문제를 풀어 보겠습니다. find duplicate number 의 경우 영상에서 친절하게 동영상으로 설명하고 있기 때문에 저는 algo expert 의 find loop 를 이 알고리즘으로 풀어보겠습니다.

head = 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6
                           ^         V
                           9 <- 8 <- 7

위와 같은 linked list 가 있습니다.

• singly linked list 입니다. (단방향) 따라서 한 쪽 방향으로만 순회 가능!
• 반드시 딱 한 개의 loop 가 존재합니다.
• node 가 가지고 있는 숫자 값은 중복될 수 있습니다. 예를 들어 2 가 두 번 나올 수 있습니다.

linked list 안에 한 개의 loop 가 있다고 합시다. 이 loop 의 시작 node를 반환하는 함수를 작성하는 것이 문제입니다. 위의 예제에서는 value 가 4인 node 를 반환하면 되겠죠. 단! O(N) 이상의 공간 복잡도를 사용하면 안 됩니다. (N 은 노드 개수)

문제에 접근하기

공간 복잡도의 제약 때문에 hash map 을 사용할 수 없습니다! (파이썬에서는 dict) 그래서 다음과 같은 방법을 사용할 겁니다.

• 시작 지점에 거북이 포인터 와 토끼 포인터 를 생성합니다.
• 거북이 포인터는 한 칸씩 노드를 이동합니다.
• 토끼 포인터는 두 칸씩 노드를 이동합니다.

문제에서 “반드시 한 개의 loop가 있다고 했습니다.” 따라서 거북이 포인터와 토끼 포인터는 루프를 돌다가 루프 안에서 만나게 됩니다.

• 토끼와 거북이가 노드 6 에서 만났다고 합시다.
• head 부터 루프의 시작노드4 까지의 거리를 D (distance) 라고 합시다.
• 루프의 시작노드 부터 토끼와 거북이가 만난 지점 6까지의 거리를 P (그냥 P ㅎㅎ..) 라고 합시다.
• 다시 토끼와 거북이가 만난 지점부터 루프의 시작 노드 까지를 R (remainder) 라고 합시다.

여기서 생각해봅시다. 거북이가 움직인 거리를 D, P, R 로 표현하면 어떻게 될까요?

• 거북이는 D + P 만큼 움직였습니다.
• 토끼는 거북이보다 2배 빠르므로, 2(D + P) 만큼, 즉 2d + 2P 만큼 움직였습니다.

문제의 해결

여기서 조금만 더 생각해 봅시다. 토끼와 거북이가 만난 지점에서 다시 루프의 시작지점으로 돌아가려면 얼마만큼 이동해야 할까요? 이 거리를 아까 R 이라고 하자 했습니다. 그런데 이 R이 사실은 D랑 똑같습니다!

왜????

토끼와 거북이가 이동한 경로를 각각 생각해 봅시다.

• 토끼: D 만큼 이동해서 루프의 시작지점에 진입. -> P 만큼 이동 -> R 만큼 이동 -> 다시 P 만큼 이동해 “토끼와 거북이가 만나는 지점” 에 안착했습니다.
• 거북이: D 만큼 이동해서 루프의 시작지점에 진입. -> P 만큼 이동 -> “토끼와 거북이가 만나는 지점” 에 안착했습니다.
  맨 처음에 토끼의 이동 거리는 2D + 2P 라고 했죠? 그리고 이번에 이동 경로를 생각해 보니 D -> P -> R -> P 만큼 이동했다는 것을 알았습니다. 따라서 2D + 2P = D + P + R + P 이므로, R = D 입니다1

그럼 이제 D 만큼 이동해 볼까요? 토끼를 head로 순간이동 시킨 뒤, 이번에는 토끼도 한 칸씩, 거북이도 한 칸씩 이동합니다. 그러면 서로 D 만큼 이동해서 둘이 다시 만나겠죠? 이 만나는 지점이 바로 루프의 시작 지점이 됩니다!

코드

# node.next 가 다음 노드를 가리킨다고 가정합니다.

def findLoop(head):
    # 거북이는 한 칸, 토끼는 두 칸 이미 이동한 상태에서 시작!
    tortoise = head.next
    hare = head.next.next
    while tortoise is not hare:
        tortoise = tortoise.next
        hare = hare.next.next
    
    # 토끼를 순간이동 시킨 뒤, 이번에는 한 칸씩 이동
    hare = head
    while tortoise is not hare:
        tortoise = tortoise.next
        hare = hare.next
    return tortoise