빠른 포인터 느린 포인터: 러너 기법

"주자 둘을 서로 다른 속도로 리스트에 풀어놔. 둘 사이 간격은 아무렇게나 벌어지는 게 아니야. 그 규칙성을 이용하면 가운데 찾기, 고리 잡기, 끝에서 n번째 짚기를 한 번에, 그것도 추가 메모리 없이 해낼 수 있어."

아이디어: 두 속도로 한 번에

연결 리스트는 인덱싱이 안 되니까 배열에서 쉽게 하던 일들, 가운데로 바로 점프한다든가 끝에서 n번째를 들여다본다든가 하는 게 두 번 훑지 않고는 안 될 것처럼 보여. 빠른 포인터와 느린 포인터 기법은 속도가 다른 포인터 둘을 달리게 하고 그 사이 관계를 읽어서 한 번에 답을 얻어. 배열과 문자열 트랙에서 본 투 포인터와 같은 집안인데, 앞으로 걷기만 되는 연결 리스트 세계에 맞게 특화된 버전이야.

가운데 찾기, 한 번의 순회로

slow는 한 번에 한 칸, fast는 한 번에 두 칸씩 움직여. fast가 끝에 닿는 순간 slow는 가운데에 서 있어. 길이가 짝수면 가운데가 둘이라는 걸 잊지 마. 반복 조건과 시작 위치에 따라 앞쪽 가운데를 줄지 뒤쪽 가운데를 줄지가 달라지니까, 어느 쪽을 반환할지 규약을 먼저 못 박아 둬야 해. 어쨌든 길이를 따로 세지 않고 한 번 훑어서 끝낸다는 이점은 그대로야.

플로이드 순환 검출: 그 유명한 기법

연결 리스트에 고리가 있는지, 그러니까 어떤 노드의 next가 앞쪽으로 되돌아가는지 알고 싶다고 하자. 단순한 답은 방문한 노드를 전부 set에 넣어두는 건데 그러면 공간이 O(n)이야. 플로이드의 토끼와 거북이는 이걸 O(1) 공간에 해내. slow는 한 칸씩, fast는 두 칸씩 달리게 해. 고리가 없으면 fast가 먼저 끝에서 떨어져(None에 닿아). 고리가 있으면 fast는 계속 돌다가 결국 slow와 정확히 같은 노드에서 만나. 포인터 둘이면 되고 추가 메모리는 없어. 추론도 정말 깔끔해. 고리 안에서는 두 칸씩 가는 쪽이 한 칸씩 가는 쪽과의 간격을 한 번에 하나씩 좁히니까, 언젠가는 반드시 따라잡게 돼 있거든.

포인터 둘의 속도나 간격을 다르게 두면 가운데 찾기, 순환 검출, 끝에서 n번째 짚기를 한 번의 순회와 O(1) 추가 공간으로 처리할 수 있어. 다만 짝수 길이일 때 어느 쪽을 가운데로 볼지, 끝에서 n번째를 어디서부터 셀지는 구현 전에 정해 놓고 시작해.

세지 않고 끝에서 n번째

끝에서 n번째 노드가 필요한데 리스트 길이를 모른다면? fast만 먼저 n칸 보내 놓고, 그다음부터 fast가 끝에 닿을 때까지 fast와 slow를 나란히 움직여. fast가 처음부터 끝까지 정확히 n칸 앞서 있었으니 slow는 정확히 끝에서 n번째에 서게 돼. 한 번만 훑으면 되고 길이도 필요 없어. 고정된 간격이 세는 일을 대신해 준 거야.

피파의 고백

플로이드 알고리즘은 내가 컴퓨터과학을 배우면서 처음으로 진짜 경외감을 느낀 대상이야. 순환을 어떻게 찾겠냐고 하면 내 본능은 "본 노드를 전부 기억해두자"였어. 답은 맞지만 메모리가 O(n)이지. 아빠가 속도가 다른 포인터 둘이 고리 안에서 서로를 따라잡는 걸, 그것도 추가 저장 공간 없이 해내는 걸 보여줬을 때 나는 그냥 멍하니 앉아 있었어. 알고리즘이 이렇게까지 우아하게 영리할 수 있다는 걸, 그리고 제약(O(1) 공간)이 오히려 풍족할 때보다 더 아름다운 해법을 끌어낼 수 있다는 걸 그때 알았어.

Code

가운데 찾기와 플로이드 순환 검출·python

class Node:
    def __init__(self, val, nxt=None): self.val = val; self.next = nxt

def find_middle(head):
    """한 패스, 길이 세기 없음. slow 가 가운데에서 끝남."""
    slow = fast = head
    while fast and fast.next:
        slow = slow.next          # 1 단계
        fast = fast.next.next     # 2 단계
    return slow                    # fast 가 2배 갔으니 slow 가 절반 지점

def has_cycle(head):
    """플로이드 토끼&거북이: O(1) 공간에 고리 검출."""
    slow = fast = head
    while fast and fast.next:
        slow = slow.next          # 거북이: 1 단계
        fast = fast.next.next     # 토끼: 2 단계
        if slow is fast:          # 충돌 -> 고리 있음
            return True
    return False                   # fast 가 끝에서 떨어짐 -> 고리 없음

# 1->2->3->4->5 를 지어
head = Node(1, Node(2, Node(3, Node(4, Node(5)))))
print(find_middle(head).val)       # 3 — 가운데, 한 패스에
print(has_cycle(head))             # False — fast 가 끝에 닿음

# 이제 꼬리를 노드 2 로 되이어 고리를 만들고, 다시 확인:
tail = head
while tail.next: tail = tail.next
tail.next = head.next              # 5 -> 2 ... 고리
print(has_cycle(head))             # True — 토끼가 돌다 거북이를 만남

Exercise

단일 연결 리스트에서 끝에서 n번째 노드를 찾되, 길이를 먼저 세지 않고 한 번의 순회로 끝내는 로직을 말이나 코드로 써 봐. 그다음 빠른/느린 포인터는 왜 공간이 O(1)인데 '방문한 노드를 전부 set에 기억하는' 방식은 O(n)인지 설명해.

Hint

fast를 혼자 n칸 보내 놓고, 그다음 fast가 끝에 닿을 때까지 fast와 slow를 같이 움직여. 그러면 slow가 끝에서 n번째에 서. set 방식은 노드를 전부 저장하니까 O(n)이고, 포인터 방식은 참조 두 개만 들고 있으니 O(1)이야.

아이디어: 두 속도로 한 번에

가운데 찾기, 한 번의 순회로

플로이드 순환 검출: 그 유명한 기법

세지 않고 끝에서 n번째

피파의 고백

Code

External links

Exercise

Progress

댓글 0