플로이드의 토끼와 거북이 알고리듬(Floyd’s Cycle Detection)의 원리와 구현 - soo:bak

작성일 :

개요

토끼와 거북이 알고리듬(Floyd’s Cycle Detection)은

유한한 상태 공간내의 반복적으로 값을 전이시키는 구조 안에서 사이클(순환)이 존재하는지를 빠르게 확인할 수 있는 방법입니다.

이 방식은 연결 리스트, 수열, 함수 기반 전이 등 다양한 문제에 사용되며,

사이클의 존재 여부는 물론 사이클의 시작점과 길이까지 효율적으로 구할 수 있다는 특징이 있습니다.


문제 상황 예시

다음과 같은 조건이 주어졌다고 가정합니다:

  • 어떤 값 \(x\) 에서 시작하여, 정해진 함수 \(f(x)\)를 통해 다음 값을 계속 생성해 나갑니다.
  • 이 값들이 어느 시점부터 다시 이전에 등장한 값을 반복하는 구조를 가집니다.

예시 :

\(x_0\) → \(x_1\) → \(x_2\) → \(x_3\) → \(x_4\) → \(x_2\) → \(x_3\) → \(x_4\) → \(...\)

  • \(x_2\)부터는 같은 값이 반복되고 있으므로, \(x_2 \rightarrow x_3 \rightarrow x_4\)는 사이클을 형성합니다.


알고리듬의 직관

이 알고리듬은 다음과 같은 방식으로 작동합니다:

  • 두 개의 포인터를 사용합니다.
  • 하나는 한 번에 한 칸씩 이동하는 거북이(slow pointer),
  • 다른 하나는 한 번에 두 칸씩 이동하는 토끼(fast pointer)입니다.


사이클이 없다면 두 포인터는 서로 만나지 않고 종료됩니다.

하지만 사이클이 존재한다면, 빠르게 이동하는 포인터는 언젠가 느리게 이동하는 포인터와 같은 지점에서 만나게 됩니다.


알고리듬 단계 요약

토끼와 거북이 알고리듬은 사이클의 존재 여부만 판별하는 것이 아니라,

사이클의 시작점과 그 길이까지 함께 찾을 수 있는 구조입니다.

전체 흐름은 다음과 같이 세 단계로 나눌 수 있습니다:

  1. 사이클 존재 여부 판별

    • 두 포인터를 이동시켜 같은 지점에 도달하는지 확인합니다.
    • slow는 한 칸씩, fast는 두 칸씩 이동하며 값을 비교합니다.
    • 값이 일치하면, 사이클이 존재하는 것입니다.

  2. 사이클 시작점 찾기

    • 처음 지점에서 다시 포인터를 하나 두고,
      만났던 지점에서 다른 포인터를 출발시켜 같은 속도로 이동합니다.
    • 두 포인터가 만나는 지점이 바로 사이클의 시작점입니다.

  3. 사이클 길이 계산

    • 사이클 시작 지점에서 다시 한 바퀴 순회하며
      돌아올 때까지 이동한 횟수를 세면 사이클의 길이를 알 수 있습니다.


예제 수열로 확인하기

예제 수열 : \(f(x) = (x^2 + 1) \bmod 255\)

초기값: \(x_0 = 3\)

이 함수는 현재의 값을 기반으로 다음 상태를 만들어내는 전형적인 함수 기반 수열입니다.

이 수열을 반복적으로 적용하면 일정 시점부터 같은 값이 다시 등장하게 되고,

이후로는 동일한 값들이 반복되는 순환 구조로 이어집니다.

이처럼 입력값이 고정되어 있고, 가능한 상태의 수가 유한하다면

언젠가는 반드시 이전에 등장했던 값으로 되돌아가게 되며,

그 지점부터 사이클이 형성됩니다.

예를 들어 다음과 같은 흐름을 생각해볼 수 있습니다:

3 → 10 → 101 → 2 → 5 → 26 → 167 → 167 → ...

  • 이 경우 167이 반복되기 시작하는 지점이 바로 사이클 진입점이자 시작점입니다.
  • 반복되기 전까지의 구간은 비순환 구간, 이후는 사이클 구간입니다.

이러한 흐름을 통해 알고리듬의 세 단계를 실제로 어떻게 적용할 수 있는지를 구조적으로 이해할 수 있습니다.

C++ 구현 예시

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

int f(int x) {
  return (x * x + 1) % 255;
}

int FindCycleStart(int x0) {
  int slow = f(x0), fast = f(f(x0));

  while (slow != fast) {
    slow = f(slow);
    fast = f(f(fast));
  }

  int start = x0, meet = slow;
  while (start != meet) {
    start = f(start);
    meet = f(meet);
  }

  return start;
}

int CycleLength(int entry) {
  int cnt = 1, cur = f(entry);
  while (cur != entry) {
    cur = f(cur);
    cnt++;
  }
  return cnt;
}


위 코드에서 f(x) 함수는 예제 수열에 등장한 \(f(x) = (x^2 + 1) \bmod 255\) 를 그대로 구현한 것으로,

입력값 x를 받아 다음 값을 계산하는 상태 전이 함수 역할을 합니다.

  • FindCycleStart 함수는 토끼와 거북이 포인터를 이동시키며 사이클 진입점을 탐색합니다.
  • CycleLength 함수는 진입점에서 출발하여 다시 같은 위치로 돌아올 때까지 이동하면서 사이클 길이를 측정합니다.

예제 흐름과 함께 코드를 대응해 보면,

앞서 설명한 알고리듬의 세 단계를 실제 코드로 어떻게 구성할 수 있는지를 명확하게 이해할 수 있습니다.


시간 복잡도 분석

토끼와 거북이 알고리듬은 사이클 탐지 과정에서 포인터를 이동시키는 방식으로 작동하며,

전체 탐색 횟수는 비순환 구간과 순환 구간을 합한 길이에 비례합니다.

  • \(\mu\): 사이클에 진입하기 전까지의 비순환 구간 길이
  • \(\lambda\): 사이클 내부에서 반복되는 순환 구간의 길이

따라서 이 알고리듬이 수행하는 이동 횟수의 상한은 \(\mu + \lambda\)이며,

이는 전체 상태 전이 과정에서 최대 반복 길이와 일치합니다.

  • 시간 복잡도: \(O(\mu + \lambda) = O(n)\) 여기서 \(n\)은 가능한 상태 수의 최대치이며,
    일반적으로 수열의 길이 또는 연결 리스트의 길이에 해당합니다.

  • 공간 복잡도: \(O(1)\) 별도의 배열이나 자료구조 없이 포인터 두 개만으로 구현이 가능하기 때문에 매우 효율적입니다.

이 알고리듬은 시간 대비 공간 효율이 뛰어난 대표적인 기법으로,

많은 순환 구조 기반 문제에서 정석처럼 활용됩니다.


적용 예시

  • 연결 리스트 사이클 검출 연결된 노드들을 따라가며 같은 노드에 재방문하는지 확인하는 데 사용됩니다.

  • 함수 기반 수열의 주기 감지 입력값을 기반으로 다음 상태를 생성하는 수열에서, 어느 시점부터 값이 반복되는지를 찾는 데 유용합니다.

  • 난수 생성기 상태 순환 분석 난수 함수 내부에서 상태가 고정된 범위 내에서 반복되는 경우, 주기를 감지하여 안정성과 품질을 확인하는 데 응용됩니다.

  • 순열 탐색 문제에서의 사이클 분석 각 원소가 정해진 위치를 가리키는 형태의 순열 구조에서도 사이클 개수나 길이를 구하는 데 활용됩니다.


마무리

토끼와 거북이 알고리듬은 간결하면서도 강력한 사이클 탐지 기법입니다.

함수형 수열, 포인터 기반 구조, 순환 탐지가 필요한 문제에서 널리 활용되며,

단순한 반복 구조에서 주기를 찾는 문제부터 연결 리스트의 루프 판별에 이르기까지 매우 폭넓게 적용됩니다.

별도의 배열 없이도 정확하게 순환 여부를 판단할 수 있고,

사이클의 진입점과 길이까지 구할 수 있다는 점에서 실용성과 정확성 모두를 갖춘 알고리듬입니다.

이 블로그의 다른 글