도입
코딩테스트에서 투 포인터(Two-Pointer)는 가장 자주 등장하는 최적화 패턴 중 하나입니다. 브루트포스로는 O(N^2)가 걸릴 문제를 포인터 두 개의 이동 규칙만으로 O(N) 또는 O(N log N) 수준까지 줄일 수 있기 때문입니다.
특히 정렬된 배열의 쌍 찾기, 부분합 구간, 중복 없는 부분 문자열, 연결 리스트의 중간 노드 찾기처럼 “두 지점 사이 관계”가 중요한 문제에서 매우 강합니다. 다만 아무 문제에나 기계적으로 적용할 수 있는 기법은 아니고, 포인터 이동이 단조롭게 설계되는가가 성패를 가릅니다.
필요성
배열에서 두 수의 합, 구간합, 특정 조건을 만족하는 가장 짧은 부분 배열, 중복 없는 가장 긴 부분 문자열 같은 문제는 겉보기에는 모두 다른 유형처럼 보입니다. 하지만 실제로는 “왼쪽과 오른쪽 경계가 어떻게 움직여야 하는가”라는 공통 질문으로 정리되는 경우가 많습니다.
투 포인터를 모르면 이런 문제를 대부분 for문 두세 겹으로 풀게 됩니다. 반면 투 포인터를 익히면 각 포인터가 뒤로 가지 않도록 설계해 총 이동 횟수를 O(N)으로 제한할 수 있습니다. 알고리즘 문제에서 이 차이는 체감상 매우 큽니다.
- 정렬 배열에서 합이 특정 값이 되는 두 수 찾기
- 부분합이 조건을 만족하는 최소/최대 구간 찾기
- 중복 없는 가장 긴 부분 문자열
- 연결 리스트의 중간 노드 / 사이클 탐지
- 두 배열 병합, 중복 제거, partition 류 문제
정의
투 포인터의 가장 일반적인 형태는 배열이나 문자열에서 left, right 두 인덱스를 두고 움직이는 방식입니다. 하지만 연결 리스트에서 fast/slow pointer를 사용하는 것도 넓게 보면 같은 계열의 사고방식입니다.
즉, 투 포인터는 특정 구현 하나를 뜻하는 이름이 아니라, 두 개의 위치를 동시에 추적하면서 문제를 푸는 설계 패턴입니다. 그래서 문제에 따라 양끝에서 좁혀 올 수도 있고, 같은 방향으로 창문처럼 밀어도 되고, 속도를 다르게 움직일 수도 있습니다.
핵심 원리
많은 투 포인터 문제는 겉으로 보면 중첩 반복처럼 보이지만, 실제로는 포인터 하나하나가 배열 전체를 한 번씩만 훑습니다. 예를 들어 left와 right가 둘 다 0에서 시작해 오른쪽으로만 이동한다면, 각 포인터는 최대 N번만 움직입니다.
이 성질 때문에 내부에 while이 있어도 전체 시간 복잡도는 O(N)이 되는 경우가 많습니다. 투 포인터를 판별하는 핵심 감각도 바로 이것입니다. 포인터 이동이 되돌아가지 않고 누적 이동량이 선형으로 묶이는가를 보면 됩니다.
투 포인터가 성립하기 쉬운 조건
- 포인터 이동 방향이 단조롭다
- 한 번 버린 구간을 다시 볼 필요가 없다
- 현재 상태로 다음 이동을 결정할 수 있다
- 정렬 또는 구간의 단조성 같은 구조가 있다기본 구조
| 유형 | 포인터 움직임 | 대표 문제 | 핵심 전제 |
|---|---|---|---|
| 양끝 포인터 | 왼쪽과 오른쪽이 서로를 향해 이동 | 정렬 배열에서 합 찾기 | 정렬 또는 비교 기준의 단조성 |
| 슬라이딩 윈도우형 | 둘 다 같은 방향으로 이동 | 구간합, 부분 문자열, 최소 길이 구간 | 구간 조건이 포인터 이동에 따라 관리 가능 |
| Fast / Slow | 한 포인터가 더 빠르게 이동 | 연결 리스트 중간 찾기, 사이클 탐지 | 연결 구조에서 위치 차이를 활용 가능 |
기본 구현
// 1) 양끝 포인터 기본형
int left = 0;
int right = arr.length - 1;
while (left < right) {
int value = arr[left] + arr[right];
if (value == target) {
break;
} else if (value < target) {
left++;
} else {
right--;
}
}// 2) 슬라이딩 윈도우 기본형
int left = 0;
long sum = 0;
for (int right = 0; right < arr.length; right++) {
sum += arr[right];
while (sum >= target) {
// 현재 [left, right] 구간 처리
sum -= arr[left++];
}
}// 3) fast / slow 기본형 (연결 리스트)
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}패턴 1. 정렬 배열 양끝 포인터
예를 들어 정렬 배열에서 합이 target인 두 수를 찾는 문제를 생각해 보겠습니다. 현재 합이 너무 작으면 더 큰 값을 만들기 위해 왼쪽 포인터를 오른쪽으로 이동하고, 현재 합이 너무 크면 더 작은 값을 만들기 위해 오른쪽 포인터를 왼쪽으로 이동하면 됩니다.
이 패턴이 가능한 이유는 배열이 정렬되어 있기 때문입니다. 정렬이 없으면 “어느 쪽을 움직여야 더 커지거나 작아지는지”를 보장할 수 없으므로 이 논리가 성립하지 않습니다.
int[] arr = {1, 2, 4, 7, 11, 15};
int target = 15;
int left = 0;
int right = arr.length - 1;
boolean found = false;
while (left < right) {
int sum = arr[left] + arr[right];
if (sum == target) {
found = true;
System.out.println(left + " " + right);
break;
} else if (sum < target) {
left++;
} else {
right--;
}
}이 방식은 두 포인터가 각각 한 번씩만 안쪽으로 이동하므로 O(N)입니다. 다만 입력이 정렬되지 않았다면 먼저 정렬이 필요하므로 전체는 O(N log N)이 될 수 있고, 원래 인덱스가 중요하면 정렬 과정에서 별도 정보 보존이 필요합니다.
패턴 2. 슬라이딩 윈도우형 투 포인터
슬라이딩 윈도우는 넓게 보면 같은 방향 투 포인터입니다. right를 늘려 구간을 확장하고, 조건을 만족하지 않거나 너무 넓어졌다면 left를 움직여 구간을 줄입니다.
대표적으로 “합이 S 이상인 가장 짧은 부분 배열”, “중복 없는 가장 긴 부분 문자열”, “K개 이하 다른 문자만 포함하는 가장 긴 구간” 같은 문제가 여기에 속합니다. 핵심은 현재 구간 상태를 증분 업데이트할 수 있어야 한다는 점입니다.
// 양수 배열에서 합이 target 이상인 최소 길이
int[] arr = {2, 3, 1, 2, 4, 3};
int target = 7;
int left = 0;
long sum = 0;
int answer = Integer.MAX_VALUE;
for (int right = 0; right < arr.length; right++) {
sum += arr[right];
while (sum >= target) {
answer = Math.min(answer, right - left + 1);
sum -= arr[left++];
}
}
System.out.println(answer == Integer.MAX_VALUE ? 0 : answer);패턴 3. 빠른 포인터와 느린 포인터
연결 리스트는 임의 접근이 어렵기 때문에 배열처럼 양끝 포인터를 쓰기 쉽지 않습니다. 대신 slow는 한 칸씩, fast는 두 칸씩 움직이면 중간 노드를 찾거나 사이클을 감지할 수 있습니다.
특히 사이클 탐지에서 유명한 플로이드 알고리즘은 두 포인터의 상대 속도 차이를 이용합니다. 사이클이 있으면 언젠가는 fast와 slow가 만나고, 없으면 fast가 먼저 끝에 도달합니다.
// 연결 리스트 중간 노드 찾기
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// slow가 중간 노드를 가리킴// 연결 리스트 사이클 탐지
ListNode slow = head;
ListNode fast = head;
boolean hasCycle = false;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
hasCycle = true;
break;
}
}한계와 대체 기법
가장 대표적인 한계는 음수가 포함된 부분합 문제입니다. 이 경우에는 오른쪽을 늘렸을 때 합이 커진다는 단조성이 깨지므로, 단순 슬라이딩 윈도우로는 정답을 보장하기 어렵습니다.
또한 정렬이 필요한 양끝 포인터는 원래 순서를 보존해야 하는 문제와 잘 맞지 않을 수 있습니다. 이럴 때는 해시맵, 누적합, 이분 탐색, 모노톤 큐 같은 기법이 더 적합할 수 있습니다. 즉, 투 포인터는 강력하지만 적용 조건이 맞을 때만 빠릅니다.
- 부분합 문제인데 음수가 포함됨 → 누적합, 해시맵
- 정렬하면 원래 인덱스 의미가 사라짐 → 해시 기반 보조 구조
- 포인터가 자주 되돌아가야 함 → 다른 자료구조 검토
- 구간 상태를 증분 업데이트하기 어려움 → 세그먼트 트리, prefix sum, map 등
자주 하는 실수
- 정렬이 필요한 문제인데 정렬 없이 양끝 포인터를 씀
- 음수 포함 합 문제에 슬라이딩 윈도우를 그대로 적용함
left <= right,left < right경계를 잘못 둠- 구간을 줄이기 전에 답을 갱신해야 하는지 순서를 놓침
- 포인터 이동 이유를 수식이 아니라 감으로만 처리함
- 같은 요소를 두 번 쓰면 안 되는 조건을 놓침
- 정렬 후 원래 인덱스 정보가 사라지는 문제를 무시함
풀이 루틴
- 문제가 쌍인지, 연속 구간인지, 연결 구조인지 먼저 본다.
- 정렬 여부, 양수 여부, 단조성 여부를 확인한다.
- 양끝 포인터인지, 슬라이딩 윈도우인지, fast/slow인지 유형을 정한다.
- 포인터가 언제 이동해야 하는지를 말로 먼저 정의한다.
- 현재 구간에서 유지해야 할 값(합, 빈도, 길이 등)을 정한다.
- 포인터가 뒤로 가지 않는지 확인해 총 이동 횟수가 선형인지 본다.
- 경계 조건과 답 갱신 시점을 마지막으로 점검한다.
디버깅
추천 체크리스트
- 정렬 전제 확인
- 양수 전제 확인
- left/right 이동 조건 확인
- 답 갱신 시점 확인
- while 종료 조건 확인
- 중복 원소 처리 확인
- 원래 인덱스 필요 여부 확인요약
- ✅ 투 포인터는 두 위치를 함께 움직이며 탐색 범위를 줄이는 기법이다.
- ✅ 양끝 포인터, 슬라이딩 윈도우, fast/slow pointer로 나눠 보면 구조가 잘 보인다.
- ✅ 각 포인터가 뒤로 가지 않으면 총 이동량이 선형으로 묶여
O(N)이 되기 쉽다. - ✅ 정렬 배열 쌍 문제에서는 양끝 포인터가 매우 강력하다.
- ✅ 연속 구간 문제에서는 슬라이딩 윈도우형 투 포인터가 자주 쓰인다.
- ✅ 연결 리스트에서는 fast/slow pointer가 대표적인 변형이다.
- ✅ 음수 포함 부분합처럼 단조성이 깨지면 다른 기법이 더 적합할 수 있다.
- ✅ 투 포인터는 구현보다 적용 조건과 불변식을 먼저 읽는 것이 중요하다.