핵심 정리
| 형태 | 포인터 움직임 | 대표 문제 |
|---|---|---|
| 양끝 수렴 | left++ 또는 right-- | 정렬 배열의 두 수 합 |
| 같은 방향 | right++, 조건 깨지면 left++ | 구간 조건 유지 |
| 빠른/느린 포인터 | 속도가 다른 두 포인터 | 사이클, 중간 노드 |
csharp
int left = 0;
int right = arr.Length - 1;
while (left < right)
{
int sum = arr[left] + arr[right];
if (sum == target) return true;
if (sum < target) left++;
else right--;
}구조
투 포인터는 모든 쌍을 다 보지 않고, 두 위치를 움직이며 후보를 줄이는 패턴입니다. 정렬 배열에서 두 수의 합을 찾는 문제를 O(n²)에서 O(n)으로 줄일 수 있습니다.
정렬되어 있으면 합이 작을 때 왼쪽을 오른쪽으로 옮겨 값을 키우고, 합이 클 때 오른쪽을 왼쪽으로 옮겨 값을 줄일 수 있습니다. 이 단조성이 투 포인터의 근거입니다.
text
합이 작음 -> 더 큰 값 필요 -> left 증가
합이 큼 -> 더 작은 값 필요 -> right 감소같은 방향 포인터
두 포인터가 같은 방향으로 움직이는 형태는 구간을 유지하면서 조건을 맞출 때 자주 씁니다.
csharp
int left = 0;
int sum = 0;
for (int right = 0; right < arr.Length; right++)
{
sum += arr[right];
while (sum > limit)
{
sum -= arr[left];
left++;
}
}선택 기준
| 문제 신호 | 판단 |
|---|---|
| 정렬 배열에서 두 값 조합 | 양끝 투 포인터 |
| 연속 구간 유지 | sliding window와 함께 검토 |
| 모든 쌍 O(n²)이 부담 | 투 포인터 후보 |
| 정렬하면 조건이 단조로워짐 | 정렬 + 투 포인터 |
| 포인터가 뒤로 돌아가야 함 | 다른 탐색 필요 |
투 포인터가 성립하려면 포인터를 움직였을 때 버리는 후보가 정말 답이 될 수 없어야 합니다. 이 근거가 없으면 우연히 예제만 맞는 풀이가 됩니다.
주의할 점
정렬이 필요한 투 포인터에서 원래 인덱스가 답에 필요하면 값과 인덱스를 함께 저장해야 합니다.
또 음수, 중복, 같은 원소 두 번 사용 금지 조건을 놓치면 경계가 틀어집니다. left < right인지, left <= right인지 먼저 고정하세요.