two-pointer 기법이란 무엇인가요?

Question

Accepted Answer

**Two-pointer** 기법은 시퀀스를 따라 이동하는 두 개의 인덱스를 사용하여 한 번의 순회로 문제를 해결합니다 — 많은 O(n²) 무차별 대입 해법을 **O(n)**으로 바꿉니다.

## 개념

두 포인터(보통 양 끝, 또는 느린 포인터 하나와 빠른 포인터 하나)를 유지하고 조건에 따라 이동시켜, 다시 스캔하지 않으면서 작업을 줄여 나갑니다.

## 예시: 정렬된 배열에서 목표 합이 되는 쌍 찾기

```python
def two_sum_sorted(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo < hi:
        s = arr[lo] + arr[hi]
        if s == target:
            return (lo, hi)       # 쌍을 찾음
        elif s < target:
            lo += 1               # 더 큰 합이 필요
        else:
            hi -= 1               # 더 작은 합이 필요
    return None

two_sum_sorted([1, 3, 4, 6, 9], 10)   # -> (1, 3), 즉 4 + 6
```

## 복잡도

- **시간:** O(n). **공간:** O(1).

## 언제 사용하나 / 함정

**정렬된 배열**, 회문 확인, 뒤집기, 제자리 중복 제거에 좋습니다. 수렴 포인터 변형에서는 배열이 정렬되어 있어야 하는 경우가 많습니다. 포인터 경계와 루프 조건(`lo < hi`)을 주의하세요.

## 왜 중요한가

Two-pointer는 가장 효과가 큰 면접 패턴 중 하나입니다. 중첩 루프를 깔끔한 선형 순회로 축소합니다.

무차별 대입 대신 구조(예: 정렬됨)를 활용하는 법을 가르쳐 줍니다.

같은 아이디어가 병합, 분할, 그리고 merge sort의 병합 단계를 뒷받침합니다.