Quick Flow
정렬된 배열에서 양끝을 좁힐 때는 합이 작으면 왼쪽, 크면 오른쪽을 움직입니다. 이 결정을 정당화하는 정렬 또는 단조성이 없으면 투 포인터로 후보를 버리면 안 됩니다.
static bool HasPairWithSum(int[] sorted, int target)
{
int left = 0;
int right = sorted.Length - 1;
while (left < right)
{
long sum = (long)sorted[left] + sorted[right];
if (sum == target) return true;
if (sum < target) left++;
else right--;
}
return false;
}- 정렬 배열의 두 값 조합: 양끝 수렴
- 음수가 아닌 배열의 합·길이 조건: 같은 방향 슬라이딩 윈도우
- 연결 리스트 사이클·중간 노드: 빠른/느린 포인터
구조
투 포인터는 모든 쌍을 다 보지 않고, 두 위치를 움직이며 후보를 줄이는 패턴입니다. 정렬 배열에서 두 수의 합을 찾는 문제를 O(n²)에서 O(n)으로 줄일 수 있습니다.
정렬되어 있으면 합이 작을 때 왼쪽을 오른쪽으로 옮겨 값을 키우고, 합이 클 때 오른쪽을 왼쪽으로 옮겨 값을 줄일 수 있습니다. 이 단조성이 투 포인터의 근거입니다.
합이 작음 -> 더 큰 값 필요 -> left 증가
합이 큼 -> 더 작은 값 필요 -> right 감소같은 방향 포인터
두 포인터가 같은 방향으로 움직이는 형태는 구간을 유지하면서 조건을 맞출 때 자주 씁니다. 합이 제한을 넘으면 왼쪽을 줄여도 합이 커지지 않아야 하므로, 합 조건에는 원소가 음수가 아니라는 전제가 필요합니다.
static int LongestWindowWithSumAtMost(int[] values, int limit)
{
if (limit < 0) return 0;
int left = 0;
long sum = 0;
int longest = 0;
for (int right = 0; right < values.Length; right++)
{
if (values[right] < 0) throw new ArgumentException("음수는 이 패턴의 전제를 깹니다.");
sum += values[right];
while (sum > limit)
{
sum -= values[left];
left++;
}
longest = Math.Max(longest, right - left + 1);
}
return longest;
}음수가 있으면 오른쪽 값을 추가한 뒤 합이 커졌다가, 왼쪽을 줄였을 때 다시 커질 수 있습니다. 이때는 현재 창을 버려도 되는 근거가 없으므로 prefix sum과 해시, 이분 탐색, 별도 DP 같은 문제 조건에 맞는 방법을 고릅니다.
빠른/느린 포인터
연결 리스트에서는 한 포인터를 한 칸, 다른 포인터를 두 칸 움직입니다. 빠른 포인터가 끝에 닿으면 사이클이 없고, 같은 노드를 만나면 사이클이 있습니다.
sealed class ListNode
{
public ListNode? Next;
}
static bool HasCycle(ListNode? head)
{
ListNode? slow = head;
ListNode? fast = head;
while (fast?.Next != null)
{
slow = slow!.Next;
fast = fast.Next.Next;
if (slow == fast) return true;
}
return false;
}선택 기준
| 문제 신호 | 판단 |
|---|---|
| 정렬 배열에서 두 값 조합 | 양끝 투 포인터 |
| 연속 구간 유지 | sliding window와 함께 검토 |
| 모든 쌍 O(n²)이 부담 | 투 포인터 후보 |
| 정렬하면 조건이 단조로워짐 | 정렬 + 투 포인터 |
| 포인터가 뒤로 돌아가야 함 | 다른 탐색 필요 |
투 포인터가 성립하려면 포인터를 움직였을 때 버리는 후보가 정말 답이 될 수 없어야 합니다. 이 근거가 없으면 우연히 예제만 맞는 풀이가 됩니다.
주의할 점
정렬이 필요한 투 포인터에서 원래 인덱스가 답에 필요하면 값과 인덱스를 함께 저장해야 합니다.
또 음수, 중복, 같은 원소 두 번 사용 금지 조건을 놓치면 경계가 틀어집니다. 정렬 뒤 원래 인덱스가 필요하면 (Value, Index)를 함께 정렬하고, 서로 다른 두 원소를 요구하면 left < right를 유지하세요.
참고 링크
1 sources