알고리즘 - 5. 빠른 포인터와 느린 포인터

빠른 포인터와 느린 포인터를 사용하는 경우

빠른 포인터와 느린 포인터는 패턴을 감지하거나 특정 위치를 찾기 위해 서로 다른 속도로 연결 리스트를 탐색해야 할 때 사용합니다. 사이클 감지에 가장 일반적으로 사용되지만 다음과 같은 용도로도 활용할 수 있습니다:

• 사이클 감지 (고전적 사용 사례 - 플로이드의 사이클 감지)
• 한 번의 순회로 연결 리스트의 중간 노드 찾기
• 연결 리스트에서 사이클의 시작점 찾기
• 끝에서 k번째 노드 감지 (간격을 유지함으로써)
• 연결 리스트에서 회문 시퀀스 찾기
• 서로 다른 속도로 위치를 비교하여 숨겨진 구조를 드러내는 문제

예제 문제

결함이 있는 생산 라인: 공장의 원형 컨베이어 벨트에서 제품들이 일렬로 이동한다고 상상해보세요. 트랙의 결함으로 인해 일부 제품이 이전 지점으로 다시 돌아갈 수 있습니다.

라인의 제품을 나타내는 연결 리스트가 주어졌을 때: 1 → 2 → 3 → 4 → 5 → 3 (루프백), 다음을 판단하세요:

1. 생산 라인에 루프가 있나요?
2. 루프는 어디서 시작하나요?

답: 예, 루프가 있으며 노드 3에서 시작합니다.

가장 중요한 통찰

서로 다른 속도로 이동하면 사이클 내에서 만남이 보장된다 - 두 포인터가 연결 리스트를 순회할 때 하나가 다른 하나의 두 배 속도로 이동하면, 사이클이 있을 경우 결국 사이클 내에서 만나게 되고, 사이클이 없으면 자연스럽게 끝에서 멈춥니다.

핵심 노트: 알고리즘의 천재성은 속도 차이에 있습니다. 빠른 포인터는 느린 포인터가 1단계 이동하는 동안 2단계를 이동합니다. 사이클 내에서 이는 빠른 포인터가 예측 가능한 속도로 느린 포인터를 따라잡는 "추격"을 만들어냅니다. 사이클이 없으면 빠른 포인터가 단순히 먼저 끝에 도달합니다. 이 간단한 속도 차이가 추가 메모리 없이 사이클 구조를 드러냅니다.

의사결정 프레임워크

순회의 각 단계에서 알고리즘은 다음과 같은 간단한 검사를 수행합니다:

• 빠른 포인터가 끝에 도달했나? (null 또는 next가 null) → 사이클이 존재하지 않음
• 빠른 포인터와 느린 포인터가 같은 노드를 가리키나? → 사이클 감지됨
• 위 조건 중 하나가 충족될 때까지 서로 다른 속도로 계속 이동

코드

연결 리스트의 중간 찾기

class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val: number) {
    this.val = val;
    this.next = null;
  }
}

// 두 포인터로 연결 리스트의 중간을 찾습니다.
// 시간: O(n), 공간: O(1)
function middleOfList(head: ListNode | null): ListNode | null {
  let slowPointer = head;
  let fastPointer = head;

  // 의사결정 프레임워크: 빠른 포인터가 끝에 도달할 때까지 계속
  while (
    fastPointer != null &&
    fastPointer.next != null &&
    // 조건에 slowPointer를 포함하면 TypeScript가 둘 다 null이 아님을 이해하는 데 도움이 됩니다
    // 참고: 논리적으로 fastPointer가 null이 아니면 slowPointer도 null이 아닙니다
    slowPointer != null
  ) {
    slowPointer = slowPointer.next;
    // 빠른 포인터를 2단계 앞으로 이동
    fastPointer = fastPointer.next.next;
  }

  // 빠른 포인터가 끝에 도달했을 때, 느린 포인터는 중간에 있음
  return slowPointer;
}

// 사용 예:
// 리스트: 1 → 2 → 3 → 4 → 5
// 빠른 포인터가 5에 있을 때, 느린 포인터는 3(중간)에 있음

사이클 존재 여부 감지

// 연결 리스트에 사이클이 포함되어 있는지 판단합니다.
// 시간: O(n), 공간: O(1)
function hasCycle(head: ListNode | null): boolean {
  let slowPointer = head;
  let fastPointer = head;

  // 의사결정 프레임워크: 포인터가 만나거나 빠른 포인터가 끝에 도달할 때까지 계속
  while (
    fastPointer != null &&
    fastPointer.next != null &&
    // 조건에 slowPointer를 포함하면 TypeScript가 둘 다 null이 아님을 이해하는 데 도움이 됩니다
    slowPointer != null
  ) {
    slowPointer = slowPointer.next;

    // 빠른 포인터를 2단계 앞으로 이동
    fastPointer = fastPointer.next.next;

    // 포인터가 만났는지 확인 (사이클 감지)
    const pointersMetAtSameNode = slowPointer === fastPointer;
    if (pointersMetAtSameNode) {
      return true;
    }
  }

  // 빠른 포인터가 끝에 도달 - 사이클이 존재하지 않음
  return false;
}

// 사용 예:
// 사이클이 있는 리스트: 1 → 2 → 3 → 4 → 5 → 3 (루프백)
// 결과: true

사이클의 시작점 찾기

// 연결 리스트에 사이클이 포함되어 있는지 판단하고
// 사이클의 시작 부분을 반환합니다. 그렇지 않으면 null을 반환합니다.
// 시간: O(n), 공간: O(1)
function cycleStart(head: ListNode | null): ListNode | null {
  let slowPointer = head;
  let fastPointer = head;

  // 단계 1: 서로 다른 속도를 사용하여 사이클 존재 감지
  while (
    fastPointer != null &&
    fastPointer.next != null &&
    slowPointer != null
  ) {
    // 루프 조건에서 TypeScript는 이제 slowPointer가 null이 아님을 알 수 있습니다
    slowPointer = slowPointer.next;

    // 빠른 포인터를 2단계 앞으로 이동
    fastPointer = fastPointer.next.next;

    // 포인터가 사이클 내에서 만났는지 확인
    const pointersMetAtSameNode = slowPointer === fastPointer;
    if (pointersMetAtSameNode) {
      break; // 사이클 감지, 단계 2로 진행
    }
  }

  // 사이클이 존재하지 않아서 종료했는지 확인
  const fastPointerReachedEnd = fastPointer == null || fastPointer.next == null;
  if (fastPointerReachedEnd) {
    return null;
  }

  // 단계 2: 사이클의 정확한 시작점 찾기
  // 수학적 속성: 헤드에서 사이클 시작점까지의 거리는
  // 만남 지점에서 사이클 시작점까지의 거리(사이클을 통해 앞으로 이동할 때)와 같습니다
  // - (자세한 내용은 아래 섹션 참조)
  //
  // 리스트 예제: 1 → 2 → 3 → 4 → 5 → 6 → 3 (사이클은 노드 3에서 시작)
  //   - 비사이클 부분: 1 → 2 (길이 = 2)
  //   - 사이클 부분: 3 → 4 → 5 → 6 → 3 (길이 = 4)
  //   - 만남 지점: 노드 5 (느린 포인터와 빠른 포인터가 처음 만나는 곳)
  //
  //   헤드(1)에서 사이클 시작(3)까지의 거리: 2단계
  //   만남 지점(5)에서 사이클 시작(3)까지의 거리: 5→6→3 = 2단계
  //   이 거리는 항상 같습니다!

  // 의사결정 프레임워크: 한 포인터를 헤드로 리셋하고, 둘 다 같은 속도로 이동
  let pointerAtMeetingPoint = slowPointer;
  let pointerAtHead = head;

  while (
    pointerAtHead != null &&
    pointerAtMeetingPoint != null &&
    // 두 포인터가 사이클 시작점에서 만날 때까지 계속
    pointerAtMeetingPoint != pointerAtHead
  ) {
    // 두 포인터를 한 번에 한 단계씩 이동 (같은 속도)
    const nextPositionFromHead = pointerAtHead.next;
    pointerAtHead = nextPositionFromHead;

    const nextPositionFromMeeting = pointerAtMeetingPoint.next;
    pointerAtMeetingPoint = nextPositionFromMeeting;
  }

  // 이제 두 포인터 모두 사이클 시작점을 가리킴
  return pointerAtHead;
}

// 사용 예:
// 리스트: 1 → 2 → 3 → 4 → 5 → 3 (노드 3이 사이클 시작)
// 결과: 값이 3인 노드

단계 2가 작동하는 이유: 수학적 증명

핵심 속성: 빠른 포인터와 느린 포인터가 사이클 내에서 만날 때, 헤드에서 사이클 시작점까지의 거리는 만남 지점에서 사이클 시작점까지의 거리(사이클을 통해 앞으로 이동)와 같습니다.

표기법

정의:

• L = 비사이클 부분의 길이 (헤드에서 사이클 시작점까지의 거리)
• C = 사이클의 길이
• k = 사이클 시작점에서 만남 지점까지의 거리 (사이클을 따라 측정)

단계 1(감지)에서 일어나는 일

포인터가 만날 때:

• 느린 포인터가 이동한 거리: L + k 단계 (사이클에 진입하기 위한 L, 만남 지점까지 k 더)
• 빠른 포인터가 이동한 거리: 2(L + k) 단계 (두 배 빠르게 이동)

빠른 포인터는 사이클 내에 있으므로, 그 위치를 다음과 같이 설명할 수도 있습니다:

• 빠른 포인터가 이동한 거리: L + k + nC 단계 (여기서 n은 완전한 루프 수)

둘 다 같은 위치에 있으므로:

2(L + k) = L + k + nC
2L + 2k = L + k + nC
L + k = nC
L = nC - k

중요한 통찰

L = nC - k에서 거리를 이해하기 위해 재배열할 수 있습니다:

만남 지점에서 사이클 시작점까지:

만남 지점은 사이클에 k 단계 들어간 위치입니다(사이클 시작점에서). 사이클 시작점으로 돌아가려면 사이클의 나머지 거리를 이동해야 합니다:

• 사이클의 나머지 거리: C - k 단계 앞으로
• 하지만 우리는 L = nC - k임을 증명했습니다

nC - k를 대수적으로 분해:

왜 nC - k = (완전한 루프) + (나머지 거리)로 쓸 수 있을까요?

나눗셈을 사용하여 이해해봅시다:

nC - k 단계를 이동해야 할 때:
  nC - k = n × C - k
         = n × C - k - C + C (- C + C = 0이므로)
         = (n-1) × C + C - k

이 분할이 의미가 있는 이유:
  nC - k = (n-1)C + C - k
         = (n-1)C + (C - k)
           ↑         ↑
      완전한     사이클 시작까지의
      루프       나머지 거리

따라서 nC - k = (완전한 루프) + (나머지 거리)

이렇게 생각해보세요:
- n개의 완전한 사이클(nC)이 있습니다
- 하지만 k(사이클 내 위치)를 뺍니다
- 이것은 (n-1)개의 완전한 루프를 취하고 (C-k)의 부분 루프를 하나 더 취하는 것과 같습니다

시각적 표현:
  사이클의 위치 k에 있고 nC - k 단계를 이동해야 하는 경우:
  - 먼저 (n-1)개의 완전한 루프를 수행합니다 (위치 k로 돌아옴)
  - 그런 다음 (C - k) 단계를 더 수행합니다 (사이클 시작점에 도달)

  이것이 nC - k가 항상 (n-1)C + (C - k)와 같은 이유입니다

핵심 깨달음: 사이클에서 nC - k 단계를 수행하는 것은 C - k 단계를 수행하는 것과 동일합니다. 왜냐하면 (n-1)C 부분은 단지 사이클을 (n-1)번 돌아 같은 위치에 도착하는 것이기 때문입니다.

따라서:

• 헤드에서 L 단계 → 사이클 시작점 도달
• 만남 지점에서 C - k 단계 → 사이클 시작점 도달
• L = nC - k이고 nC - k ≡ C - k (mod C)이므로, 이 거리들은 같습니다!

간단히 말해서: 헤드에서 L 단계 이동하는 것은 만남 지점에서 C - k 단계 이동하는 것과 같은 실제 단계 수를 필요로 합니다. 왜냐하면 nC - k의 "추가 루프"는 원형 구조에서 최종 위치를 변경하지 않기 때문입니다.

구체적인 예

리스트: 1 → 2 → 3 → 4 → 5 → 6 → 3 (사이클은 노드 3에서 시작)

설정:
- L = 2 (사이클 전 노드 1, 2)
- C = 4 (사이클: 3 → 4 → 5 → 6 → 3)

단계 1 - 만날 때까지 단계별 추적

단계 0 (시작):
  느린: [1]      빠른: [1]

단계 1:
  느린: 1 → [2]        빠른: 1 → 2 → [3]

단계 2:
  느린: 1 → 2 → [3]    빠른: 1 → 2 → 3 → 4 → [5]
  (느린 포인터가 사이클에 진입)

단계 3:
  느린: 1 → 2 → 3 → [4]          빠른: 1 → 2 → 3 → 4 → 5 → 6 → [3]
                                 (빠른 포인터가 1회 전체 루프 완료)

단계 4:
  느린: 1 → 2 → 3 → 4 → [5]      빠른: 1 → 2 → 3 → 4 → 5 → 6 → 3 → 4 → [5]

  ✓ 노드 5에서 만남!

왜 노드 5인가?

• 느린 포인터는 노드 5에 도달하는 데 4단계가 걸렸습니다
• 빠른 포인터는 노드 5에 도달하는 데 8단계가 걸렸습니다 (두 배 빠르게 이동)
• 느린 포인터가 단계 2에서 사이클에 진입한 후, 만나는 데 2단계(단계 3과 4)가 더 걸렸습니다
• 빠른 포인터는 이미 사이클을 돌고 있었고, 단계당 1노드씩 간격을 좁혔습니다

노드 5에서 만난 후:
- 느린 포인터가 이동한 거리: 4단계 (사이클 진입을 위한 L=2, 노드 5까지 k=2 더)
- 빠른 포인터가 이동한 거리: 8단계 (사이클 시작까지 2, 그 다음 6 = 사이클 1.5바퀴)
- k = 2 (사이클 시작 노드 3에서 만남 지점 노드 5까지의 거리: 3→4→5)
- 검증: L = nC - k → 2 = 1(4) - 2 ✓

단계 2 - 사이클 시작점 찾기

두 포인터가 같은 속도로 이동 (한 번에 1단계):

한 포인터를 헤드로 리셋:
  pointerAtHead: [1]
  pointerAtMeetingPoint: [5]

단계 1:
  pointerAtHead: 1 → [2]
  pointerAtMeetingPoint: 5 → [6]

단계 2:
  pointerAtHead: 1 → 2 → [3]
  pointerAtMeetingPoint: 5 → 6 → [3]

  ✓ 둘 다 노드 3(사이클 시작)에서 만남!

두 포인터는 정확히 L = 2단계를 이동하여 동시에 사이클 시작점에 도착했습니다!

시각적 증명

리스트: 1 → 2 → 3 → 4 → 5 → 6 → 3
      |___L___|_____사이클____|
              ↑           ↑
          시작(3)    만남(5)

헤드에서 시작까지의 거리: L = 2
만남에서 시작까지의 거리: (C - k) = (4 - 2) = 2

L = nC - k이고, 사이클에서 C - k만큼 앞으로 이동하므로:
L ≡ C - k (mod C)

따라서: 헤드에서 2단계 = 만남 지점에서 2단계
둘 다 동시에 사이클 시작점에 도착!

이 수학적 속성이 플로이드의 사이클 감지 알고리즘을 매우 우아하게 만듭니다 - 이 거리 동등성 때문에 단계 2가 보장되어 작동합니다.

의문 해소

일반적인 의문: "서로 다른 속도로 이동하는 것이 왜 사이클에서 포인터가 만나는 것을 보장하나요? 빠른 포인터가 느린 포인터를 계속 뛰어넘으면 어떻게 되나요?"

이것은 플로이드의 사이클 감지 알고리즘에 대한 정교한 우려입니다. 구체적인 추론으로 이를 다루어 봅시다.

빠른 포인터가 느린 포인터를 놓칠 수 있다고 생각하는 이유

연결 리스트의 사이클을 고려해보세요. 다음과 같이 생각할 수 있습니다:

• "빠른 포인터는 한 번에 2단계씩 이동하고, 느린 포인터는 1단계씩 이동한다"
• "사이클에서 빠른 포인터가 같은 노드에 착지하지 않고 느린 포인터를 뛰어넘을 수 있지 않을까?"
• "알고리즘은 그들이 만날 것으로 가정하는 것 같지만, 실제로 보장되는가?"

이러한 생각이 틀린 이유

핵심 깨달음: 각 반복마다 빠른 포인터와 느린 포인터 사이의 간격이 정확히 1노드씩 좁혀집니다!

상대 속도의 개념으로 이를 이해해봅시다:

두 포인터가 모두 사이클에 있을 때:
- 빠른 포인터 이동: 반복당 2노드
- 느린 포인터 이동: 반복당 1노드
- 상대 속도 (빠른 포인터가 느린 포인터를 따라잡음): 2 - 1 = 반복당 1노드

이는 그들 사이의 거리가 각 반복마다 정확히 1노드씩 감소함을 의미합니다.

구체적인 예: 간격은 항상 좁혀진다

5개 노드가 있는 사이클을 추적해봅시다. 느린 포인터는 위치 0, 빠른 포인터는 위치 3에 있습니다:

반복 0:
사이클: [0] → [1] → [2] → [3] → [4] → [0] (루프)
        ↑           ↑
       느린        빠른
간격: 3노드 앞

반복 1:
       [0] → [1] → [2] → [3] → [4] → [0]
              ↑                  ↑
            느린               빠른
간격: 2노드 앞 (1 감소)

반복 2:
       [0] → [1] → [2] → [3] → [4] → [0]
                     ↑    ↑
                   느린  빠른
간격: 1노드 앞 (1 감소)

반복 3:
       [0] → [1] → [2] → [3] → [4] → [0]
                          ↑
                      느린 & 빠른 만남!
간격: 0노드 (1 감소)

마법: 초기 간격 크기에 관계없이, 각 반복마다 1씩 감소한다는 것은 간격이 0에 도달했을 때 반드시 만난다는 것을 의미합니다!

보장된 만남의 수학적 증명

길이 C인 사이클에서:

• 포인터 간 초기 간격: 어떤 거리 D (0 < D < C)
• 각 반복마다 간격 감소: 1노드
• 만날 때까지의 반복: D번 반복

빠른 포인터가 느린 포인터를 "건너뛸" 수 없는 이유:

반복 N에서 간격이 2노드인 경우:

• N+1 반복 후, 간격은 1노드가 됩니다
• N+2 반복 후, 간격은 0노드가 됩니다 → 만남

상대 속도가 항상 반복당 1노드이기 때문에, 한 번의 반복으로 간격=2에서 간격=0으로 갈 방법이 없습니다.

다른 사이클 위치에서도 작동하는 이유

케이스 1: 두 포인터 모두 사이클에서 시작

• 각 반복마다 간격이 1씩 좁혀짐 → 보장된 만남

케이스 2: 포인터가 다른 시간에 사이클에 진입

• 둘 다 사이클에 있으면 케이스 1로 되돌아감
• 빠른 포인터가 먼저 진입하고 느린 포인터를 기다림
• 느린 포인터가 진입하면, 각 반복마다 간격이 1씩 좁혀짐 → 보장된 만남

플로이드 알고리즘의 탁월함

알고리즘은 세 가지 핵심 속성을 활용합니다:

1. 일정한 상대 속도: 항상 반복당 1노드
2. 원형 구조: 간격이 순환하며, 벗어날 수 없음
3. 필연적인 수렴: D의 간격은 정확히 D번 반복으로 0으로 좁혀짐

이 조합은 사이클 내에서의 만남을 보장하여 알고리즘을 우아하고 확실하게 만듭니다!

또 다른 일반적인 의문

일반적인 의문: "사이클이 극도로 크다면 - 10억 개 노드처럼요? 포인터가 만나기 전에 수십억 번 루프를 돌아야 해서 이 알고리즘이 실용적이지 않게 되지 않을까요?"

이것은 플로이드 알고리즘에 대한 정당한 성능 우려입니다. 이 두려움이 근거가 없는 이유를 살펴보겠습니다.

거대한 사이클에 대해 걱정하는 이유

사이클이 있는 거대한 연결 리스트를 고려해보세요. 다음과 같이 생각할 수 있습니다:

• "사이클에 10억 개의 노드가 있고, 포인터가 서로를 쫓아가야 한다면"
• "빠른 포인터가 마침내 만나기 전에 느린 포인터를 여러 번 추월할 수 있다"
• "이것은 수십억 번의 반복이 필요할 수 있어 실제로 O(n) 시간 복잡도를 무의미하게 만든다"

이 걱정이 불필요한 이유

핵심 깨달음: 포인터는 사이클 크기에 관계없이 최대 한 번의 완전한 순회 내에서 만납니다!

여기 중요한 통찰이 있습니다: 두 포인터가 모두 사이클 내에 들어가면, 느린 포인터가 사이클의 한 바퀴를 완료하기 전에 만납니다.

구체적인 예: 필요한 최대 반복 수

최악의 경우 분석으로 이를 증명해봅시다:

주어진 조건:
- 사이클 길이: C 노드
- 사이클 내 느린 포인터 위치: 0
- 사이클 내 빠른 포인터 위치: 1 (단 하나의 노드 앞 - 최악의 경우)

반복 추적:
간격 시작: C - 1 노드 (사이클에서 가능한 최대 간격)
간격 감소: 반복당 1노드
만날 때까지의 반복: C - 1번 반복

결과: C번 미만의 반복으로 만남 (한 전체 사이클 미만)

"거대한" 사이클의 실제 예

10개 노드의 사이클을 추적해봅시다 (10억 노드 사이클을 나타냄):

최악의 경우 시나리오:
- 사이클 길이: 10노드
- 느린 포인터 위치 0, 빠른 포인터 위치 1
- 최대 간격: 9노드

반복 0: 느린=0, 빠른=1, 간격=9
반복 1: 느린=1, 빠른=3, 간격=8
반복 2: 느린=2, 빠른=5, 간격=7
반복 3: 느린=3, 빠른=7, 간격=6
반복 4: 느린=4, 빠른=9, 간격=5
반복 5: 느린=5, 빠른=1, 간격=4 (빠른 포인터 순환)
반복 6: 느린=6, 빠른=3, 간격=3
반복 7: 느린=7, 빠른=5, 간격=2
반복 8: 느린=8, 빠른=7, 간격=1
반복 9: 느린=9, 빠른=9, 만남!

총 반복: 9 (C-1, 여기서 C=10)

절대적인 최악의 경우에도 10노드 사이클에서 단 9번의 반복으로 만났습니다!

시간 복잡도 보장

총 n개 노드가 있는 연결 리스트에 대해:

• 비사이클 부분: 길이 L 노드
• 사이클 부분: 길이 C 노드
• 합계: n = L + C 노드

단계 1 (사이클 도달):

• 느린 포인터는 사이클에 진입하는 데 L 단계 필요
• 빠른 포인터는 최대 L 단계 필요
• 반복: L

단계 2 (사이클 내에서 만남):

• 느린 포인터가 진입할 때 최대 간격: C - 1 노드
• 간격이 반복당 1씩 좁혀짐
• 반복: 최대 C - 1

총 반복: L + (C - 1) < L + C = n

이는 알고리즘이 **엄격히 O(n)**임을 증명합니다 - 10억 노드 사이클이라도 최대 한 번 순회합니다!

해시 세트를 사용하는 것보다 나은 이유

방문한 노드를 추적하는 단순한 접근법과 비교해보세요:

해시 세트 접근법:
- 시간: O(n)
- 공간: O(n) - 방문한 모든 노드 저장

빠른 & 느린 포인터:
- 시간: O(n)
- 공간: O(1) - 두 포인터만

10억 노드의 경우:
- 해시 세트는 약 8-16GB의 메모리 필요
- 빠른 & 느린 포인터는 약 16바이트만 필요 (두 포인터)

수학적 아름다움

최악의 경우 시나리오는 아름다운 속성으로 제한됩니다:

최대 반복 = n - 1

여기서 n은 총 노드 수입니다. 이는 다음을 의미합니다:

• 100노드 → 최대 99번 반복
• 1,000노드 → 최대 999번 반복
• 1,000,000,000노드 → 최대 999,999,999번 반복

"끝없이 루프"하지 않습니다 - 알고리즘은 입력 크기에 선형적으로 확장되는 엄격한 상한선을 가지고 있어 거대한 사이클에서도 매우 효율적입니다!