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

"두 러너를 다른 속도로 리스트에 보내. 그 사이 간격은 무작위가 아니야 — 가운데 찾기, 고리 잡기, 끝에서 n번째 닿기를 한 패스에 추가 메모리 없이 하려고 써먹을 수 있는 사실이야."

아이디어: 두 속도, 한 패스

연결 리스트는 인덱싱을 못 해서, 배열에서 통하는 트릭 (가운데로 점프, 끝에서 n번째 엿보기) 이 두 패스 없이는 불가능해 보여. 빠른/느린 포인터 기법은 두 포인터를 다른 속도로 달리며 그 사이 관계를 읽어 한 패스에 얻어. Arrays 트랙의 투 포인터랑 같은 가문, 걷기만 되는 연결 리스트 세계에 특화된 거야.

가운데 찾기, 한 패스에

slow 를 한 번에 한 노드, fast 를 한 번에 두 노드 움직여. fast 가 끝에 닿으면, slow 가 간 거리의 두 배를 간 거야 — 그래서 slow 가 정확히 가운데 앉아 있어. 한 순회, 길이 세기 없음, 두 번째 패스 없음. 반칙처럼 느껴지는데 그냥 산수야: 절반 속도, 절반 거리.

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

연결 리스트에 고리 (자기 next 가 리스트로 되돌아 가리키는 노드) 가 있어? 순진한 답은 방문한 모든 노드를 set 에 저장 — O(n) 공간. 플로이드의 토끼와 거북이는 O(1) 공간에 해: slow (×1) 랑 fast (×2) 를 달려. 고리가 없으면 fast 가 끝에서 떨어져 (None 에 닿음). 고리가 있으면 fast 가 계속 돌며 결국 slow 랑 정확히 같은 노드에 착지해 — 충돌해. 두 포인터, 추가 메모리 없음, 그리고 진짜 아름다운 추론: 고리 안에서 ×2 러너가 ×1 러너한테 틱당 한 칸씩 좁혀, 그래서 결국 따라잡을 수밖에 없어.

두 포인터를 다른 속도로 달리면 그 사이 고정된 간격이 도구가 돼: 가운데 (fast ×2 끝남 → slow 가 중앙), 순환 (fast 가 slow 만남 → 고리), 끝에서 n번째 (fast 가 n 앞서 시작). 한 패스, O(1) 공간.

세지 않고 끝에서 n번째

끝에서 n 위치 노드를 원하는데 길이를 몰라? fast 를 먼저 혼자 n 단계 전진시키고, 그다음 fast 가 끝에 닿을 때까지 fast 랑 slow 를 같이 움직여. fast 가 내내 정확히 n 앞에 있었어서, slow 가 정확히 끝에서 n 에 착지해. 한 패스, 길이 불필요 — 고정된 간격이 세기를 대신해줬어.

피파의 고백

플로이드 알고리즘은 나한테 실제 경외감을 느끼게 한 첫 CS 조각이었어. 순환 검출에 대한 내 본능은 "본 노드를 다 기억해" — 정답이지만 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