투 포인터란?
투 포인터(Two Pointers)는 정렬된 배열에서 두 개의 인덱스를 양 끝(또는 같은 방향)에서 움직이며 O(n)에 답을 찾는 기법입니다. 모든 쌍을 확인하는 이중 반복문 O(n²)을, 한 번의 스캔 O(n)으로 줄이는 것이 핵심입니다.
대표 예: 정렬된 배열에서 합이 target인 두 수 찾기. 왼쪽 포인터는 0, 오른쪽 포인터는 끝에서 시작합니다.
왜 O(n)에 동작하나?
배열이 정렬되어 있다는 점이 핵심입니다.
- •두 포인터가 가리키는 합이 target보다 크면 → 가장 큰 후보(오른쪽)를 줄여야 하므로
right-- - •합이 target보다 작으면 → 더 큰 값이 필요하므로
left++ - •합이 같으면 → 정답
이 단조성(한쪽을 줄이면 합이 줄고, 늘리면 합이 는다) 덕분에, 한 번 버린 후보를 다시 볼 필요가 없습니다. 그래서 각 포인터가 한 방향으로만 움직여 전체가 O(n)입니다.
동작 원리
1단계. left = 0, right = n - 1로 둡니다.
2단계. sum = arr[left] + arr[right]를 계산합니다.
3단계. sum == target이면 정답, sum > target이면 right--, sum < target이면 left++.
4단계. left < right인 동안 2~3단계를 반복합니다.
알고노트 시각화는 두 포인터가 합에 따라 안쪽으로 좁혀 오는 과정을 단계별로 보여줍니다.
시간복잡도와 공간복잡도
| 복잡도 | |
|---|---|
| 시간 | O(n) (정렬 안 됐으면 O(n log n) 선행) |
| 공간 | O(1) |
예시로 따라가기
arr = [1, 2, 4, 7, 11], target = 9.
- •left=0(1), right=4(11): 합 12 > 9 → right--
- •left=0(1), right=3(7): 합 8 < 9 → left++
- •left=1(2), right=3(7): 합 9 = 9 → 정답
(2, 7)
변형
- •같은 방향 투 포인터: 두 포인터가 같은 쪽에서 출발해 구간을 넓히고 줄이는 슬라이딩 윈도우.
- •세 수의 합: 하나를 고정하고 나머지 둘에 투 포인터.
- •중복 제거·병합: 정렬된 두 배열을 동시에 훑기.
자주 하는 실수
- •정렬 전제 무시: 정렬되지 않은 배열에 그대로 쓰면 단조성이 깨져 오답입니다.
- •경계 조건:
left < right(또는<=)를 문제에 맞게 정해야 같은 원소를 두 번 쓰지 않습니다. - •중복 쌍 처리: 모든 쌍을 찾는 문제라면 정답을 찾은 뒤 양쪽 포인터를 적절히 옮겨 중복을 건너뜁니다.
알고노트에서 직접 확인하세요
합이 target보다 크고 작음에 따라 왼쪽·오른쪽 포인터가 어떻게 움직이는지 알고노트에서 단계별로 확인할 수 있습니다.