O(1) Space 제약 하에 Deterministic 구조의 Cycle을 탐색하는 Fast and Slow Pointer 전략

Context

상태 전이가 결정론적이며 유한한 상태 공간을 가진 시스템에서 반복 구간을 탐색해야 하는 문제 상황. Hash Set을 이용한 방문 기록 방식은 상태 공간 확대에 따른 Memory Overhead가 발생하며 O(n) Space Complexity를 요구하는 한계 존재.

Technical Solution

• 서로 다른 속도로 이동하는 두 개의 Pointer를 배치하여 상대적 거리 차이를 이용한 Cycle 검출 설계
• Slow Pointer는 1단계, Fast Pointer는 2단계씩 이동하여 Cycle 존재 시 반드시 충돌하는 수학적 보장 활용
• Finite Deterministic System에서 상태 전이 함수 f(current) = next 구조를 정의하여 Linked List 외 Array 및 숫자 변환 문제로 추상화 확장
• 첫 충돌 지점 이후 한 Pointer를 Head로 리셋하고 동일 속도로 이동시켜 Cycle Entry Point를 정확히 식별하는 알고리즘 적용
• 공간 복잡도를 O(1)로 유지하면서 시간 복잡도 O(n) 내에 중복 값 및 대칭성 확인 가능

Key Takeaway

데이터 구조의 외형이 아닌 '상태 전이의 결정론적 특성'과 '유한한 상태 공간'이라는 본질적 제약에 집중하여 최적의 알고리즘 패턴을 선택하는 추상화 능력의 중요성.