리트코드 프리미엄 Slow & Fast 포인터 완벽 공략: 코테 시간 단축의 핵심 비결

코딩 테스트를 준비하다 보면 "분명 답은 알겠는데 시간 초과가 나네?" 혹은 "공간 복잡도를 어떻게 줄이지?" 하는 고민에 빠지게 됩니다. 사실 이 부분이 가장 번거로우시죠. 특히 링크드 리스트나 배열 탐색 문제에서 브루트 포스로 풀자니 효율이 떨어지고, 해시 테이블을 쓰자니 메모리가 아까운 상황이 자주 발생합니다. 막상 구글링을 해보면 '플로이드 순환 탐지' 같은 어려운 용어만 가득해서 당황스러울 때가 많은데요.

알고 보면 이 기법은 우리 일상에서 두 사람이 운동장 트랙을 달리는 모습과 아주 비슷합니다. 한 명은 천천히 걷고, 한 명은 전력 질주를 할 때 어느 지점에서 만나는지를 이용하는 것이죠. 오늘은 리트코드(LeetCode) 프리미엄에서 단골로 등장하는 이 'Slow & Fast 포인터' 패턴을 실전에서 바로 써먹을 수 있게 아주 쉽게 풀어보겠습니다.

Slow & Fast 포인터의 작동 원리 (토끼와 거북이)

이 패턴은 이름 그대로 두 개의 포인터를 사용합니다. 보통 '느린 포인터(Slow)'는 한 번에 한 칸씩 이동하고, '빠른 포인터(Fast)'는 한 번에 두 칸씩 이동하죠. 이 속도 차이가 만들어내는 마법 같은 결과가 핵심입니다.

• 추격전의 원리: 만약 데이터 구조 안에 '루프(순환)'가 있다면, 빠른 포인터는 언젠가 느린 포인터를 뒤에서 따라잡게 됩니다. 마치 400m 트랙에서 한 바퀴를 더 돌아서 만나는 것처럼요.
• 거리의 배수: 루프가 없다면 빠른 포인터가 끝에 도달했을 때, 느린 포인터는 정확히 전체 길이의 절반 지점에 위치하게 됩니다.

개인적으로 이 속도의 '비율'을 1:2로 유지하는 것이 가장 효율적이라고 생각합니다. 굳이 3칸, 4칸씩 넘어가면 리스트의 끝을 체크하는 로직만 더 복잡해지고 실수가 잦아지기 때문이죠.

실전에서 반드시 알아야 할 3가지 핵심 패턴

이 기법은 단순히 순환을 찾는 데만 쓰이지 않습니다. 리트코드 문제를 풀 때 가장 효율적인 도구가 되는 3가지 상황을 정리해 드릴게요.

1. 연결 리스트의 순환 탐지 (Cycle Detection)

가장 기본이 되는 패턴입니다. 리스트가 끝없이 반복되는 구조인지 확인하는 문제죠. 해시셋(HashSet)을 써서 노드를 저장하면 공간 복잡도가 $O(n)$이 되지만, 이 포인터 기법을 쓰면 추가 메모리 없이 $O(1)$로 해결 가능합니다. 비용 절감 측면에서 보면 메모리라는 자원을 가장 아끼는 고효율 도구인 셈이죠.

2. 중간 지점 찾기 (Middle of Linked List)

전체 길이를 모르는 상태에서 중간 노드를 찾아야 할 때 유용합니다. 빠른 포인터가 끝(null)에 닿는 순간, 느린 포인터가 가리키는 곳이 바로 중간입니다. 병합 정렬(Merge Sort)을 구현할 때 리스트를 반으로 나누는 용도로 자주 쓰입니다.

3. 순환의 시작점 찾기 (Cycle Start Point)

이건 저도 처음엔 정말 헷갈렸던 부분인데요. 두 포인터가 만난 지점에서 한 포인터를 다시 시작점(head)으로 옮기고, 둘 다 한 칸씩 이동시키면 다시 만나는 지점이 바로 순환의 시작점입니다. 이건 수학적인 증명이 뒷받침되는 공식이라 그냥 외워두시는 게 마음 편합니다.

리트코드 주요 문제 유형 비교

여러분에게 딱 맞는 최적의 연습 문제를 아래 표로 정리해 보았습니다. 난이도별로 확인해 보세요.

문제 번호	문제 이름	핵심 포인트	난이도
141	Linked List Cycle	단순 순환 여부 판별	Easy
142	Linked List Cycle II	순환이 시작되는 노드 반환	Medium
876	Middle of the Linked List	리스트 정중앙 찾기	Easy
287	Find the Duplicate Number	배열을 리스트처럼 해석하기	Medium

 
표를 보면 아시겠지만, 사실 141번과 142번은 세트로 공부하는 것이 가장 좋습니다. 141번을 풀 줄 안다면 142번은 한 끗 차이거든요. 특히 287번처럼 '배열' 문제인데도 이 패턴을 적용하는 문제는 코딩 테스트에서 변별력을 가르는 아주 좋은 문제입니다.

이 패턴이 오히려 '독'이 되는 경우

무조건 이 기법이 최고는 아닙니다. 솔직히 말씀드리면, 데이터 구조가 너무 작거나 메모리 제한이 넉넉하다면 그냥 해시셋을 쓰는 게 코드 가독성 면에서는 훨씬 낫습니다. Slow & Fast 포인터는 다음과 같은 상황에서 주의해야 해요.

• 데이터 수정이 빈번한 경우: 포인터가 이동하는 중에 리스트의 구조가 바뀌면 예측 불가능한 결과가 나옵니다.
• 단방향이 아닌 경우: 양방향 연결 리스트나 그래프에서는 더 적합한 알고리즘(BFS/DFS)이 따로 있습니다.
• 가독성 저하: 동료들과 협업할 때 이 기법을 모르는 사람이 코드를 본다면 "왜 여기서 두 칸씩 가나요?"라는 질문을 받을 수 있습니다. 이건 모르면 손해 보는 꿀팁인데, 주석으로 'Tortoise and Hare Algorithm'이라고 명시해 주는 센스가 필요합니다.

구현할 때 자주 하는 실수와 팁

이 단계에서 흔히 하는 실수는 바로 null 체크입니다. fast 포인터는 한 번에 두 칸을 이동하기 때문에 fast뿐만 아니라 fast.next가 null인지도 반드시 확인해야 합니다. 그렇지 않으면 바로 에러(NullPointerException)를 만나게 되죠.

또한, 시작 위치를 설정할 때 두 포인터를 모두 head에서 시작할지, 아니면 하나를 head.next에서 시작할지도 문제의 조건에 따라 세밀하게 조정해야 합니다. 마치 대형마트 오픈런을 준비할 때 입구가 어디인지 정확히 파악하는 것과 같습니다.

제 생각에는 루프 조건문을 작성할 때 while (fast != null && fast.next != null) 형식을 기본 템플릿으로 삼는 것이 가장 안전해 보입니다.

결국 핵심은 '통찰력'

Slow & Fast 포인터는 단순히 테크닉이 아니라, 주어진 자료 구조를 어떻게 다르게 바라볼 것인가에 대한 문제입니다. 숫자가 가득한 배열을 보고 "이건 인덱스를 포인터로 삼는 연결 리스트네?"라고 생각하는 순간, 여러분의 문제 풀이 능력은 한 단계 점프하게 됩니다.

결국 핵심은 속도가 아니라 정확한 만남의 지점을 찾는 것입니다. 리트코드 프리미엄 문제를 풀 때 이 패턴을 적용해 보면서 손에 익혀보세요. 한 번 감을 잡으면 링크드 리스트 관련 문제는 정말 '껌'처럼 느껴지실 겁니다. 여러분은 이 패턴을 처음 접했을 때 어떤 점이 가장 이해하기 어려우셨나요? 혹은 나만의 더 기발한 포인터 활용법이 있으신가요?

지금 소개한 기초적인 활용법 외에도 최근에는 2026년형 알고리즘 트렌드에 맞춰 NPU(신경망 처리 장치) 가속을 염두에 둔 포인터 최적화 기법들도 등장하고 있으니, 관심 있으신 분들은 공식 문서의 최신 업데이트를 확인해 보시는 것도 추천드립니다.

코딩 테스트 기초 체력 키우기! Codewars 7kyu 정복을 위한 깃허브 프로젝트 및 언어별 공략 총정리