투 포인터 알고리즘은 배열 문제에서 시간초과를 줄이는 대표적인 사고법입니다. 이름은 어려워 보이지만 핵심은 단순합니다. 두 개의 인덱스를 움직이면서 볼 필요가 없는 범위를 조금씩 버리는 것입니다.
중요한 건 정의를 외우는 것이 아닙니다. 어떤 문제에서 투 포인터를 먼저 떠올려야 하는지, 그리고 왜 포인터를 움직여도 답을 놓치지 않는지를 이해하는 것이 훨씬 중요합니다. 이번 글은 그 감각을 쉬운 예시로 정리합니다.
투 포인터 알고리즘
투 포인터는 배열에서 left, right 같은 두 인덱스를 두고 현재 상태를 보면서 한쪽 또는 양쪽을 움직이는 기법입니다. 하지만 포인터가 두 개라는 사실 자체보다 중요한 것은 포인터를 움직일 때 정답 후보를 안전하게 줄일 수 있어야 한다는 점입니다.
예를 들어 정렬된 배열에서 현재 합이 너무 크면 오른쪽 값을 줄이고, 현재 합이 너무 작으면 왼쪽 값을 키우는 식으로 이동할 수 있습니다. 정렬 순서 덕분에 어떤 후보를 버려도 되는지 설명할 수 있기 때문입니다.
먼저 감각
- 양끝에서 좁혀 오는 방식
- 같은 방향으로 움직이는 방식
- 둘 다 불필요한 범위를 줄이는 사고법이라는 점은 같다
첫 번째는 정렬된 배열의 쌍 문제에서 자주 나오고, 두 번째는 연속 부분 배열 문제에서 자주 나옵니다. 같은 방향 방식은 보통 슬라이딩 윈도우라고도 부릅니다.
왜 완전탐색 대신 떠올릴까
배열의 모든 두 수를 보거나, 모든 시작점과 끝점을 다 보는 방식은 직관적이지만 금방 O(n^2)가 됩니다. 입력이 커지면 그 순간 시간초과가 나기 쉽습니다.
투 포인터는 여기서 질문을 바꿉니다. 정말 모든 경우를 다 봐야 하는지, 현재 상태를 보고 이쪽은 더 볼 필요가 없다고 말할 수 있는지 확인하는 것입니다. 이 판단이 가능하면 범위를 줄이면서 훨씬 적게 탐색할 수 있습니다.
두 수의 합
가장 유명한 예시는 정렬된 배열에서 합이 target이 되는 두 수를 찾는 문제입니다. 예를 들어 [1, 2, 4, 7, 11, 15]에서 합이 15가 되는 두 수를 찾는다고 해보겠습니다.
정렬되어 있다면 left는 맨 앞, right는 맨 뒤에서 시작합니다. 현재 합이 너무 크면 right를 줄이고, 너무 작으면 left를 늘립니다. 현재 합이 너무 큰데 왼쪽을 더 키우면 합은 더 커지거나 같아질 뿐이므로, 이 경우 왼쪽을 움직일 이유가 없습니다.
정렬 때문에 한쪽을 움직였을 때 어떤 후보들이 자동으로 탈락하는지 설명할 수 있다면, 투 포인터를 쓸 가능성이 높습니다.
from typing import List, Optional, Tuple
def find_pair(nums: List[int], target: int) -> Optional[Tuple[int, int]]:
left = 0
right = len(nums) - 1
while left < right:
current = nums[left] + nums[right]
if current == target:
return nums[left], nums[right]
elif current < target:
left += 1
else:
right -= 1
return None탐색 자체는 각 포인터가 한 방향으로만 움직여 O(n)입니다. 다만 입력이 처음부터 정렬되어 있지 않다면 정렬 비용까지 포함해 보통 O(n log n)으로 생각하면 됩니다.
예시 흐름
같은 배열 [1, 2, 4, 7, 11, 15]에서 target이 15라고 해보겠습니다. 처음에는 1 + 15 = 16이라 너무 큽니다. 그러면 오른쪽 값을 줄입니다. 다음은 1 + 11 = 12라서 너무 작습니다. 이번에는 왼쪽 값을 늘립니다. 이어서 2 + 11 = 13, 다시 왼쪽을 움직이고, 마지막에 4 + 11 = 15를 찾게 됩니다.
완전탐색처럼 모든 쌍을 만들지 않았지만, 정렬 정보 덕분에 정답을 놓치지 않았습니다. 이 감각이 양끝 투 포인터의 핵심입니다.
슬라이딩 윈도우
투 포인터의 또 다른 대표 형태는 같은 방향으로 움직이는 방식입니다. 보통 연속 부분 배열 문제에서 등장하며, 슬라이딩 윈도우라고도 부릅니다. 예를 들어 합이 K 이하인 가장 긴 연속 부분 배열을 구하는 문제를 생각해볼 수 있습니다.
이때는 오른쪽 포인터를 늘리며 구간을 확장하고, 합이 너무 커지면 왼쪽 포인터를 움직여 구간을 다시 줄입니다. 구간의 합을 계속 유지할 수 있기 때문에 모든 시작점과 끝점을 새로 계산할 필요가 없습니다.
def longest_window(nums, limit):
left = 0
current_sum = 0
answer = 0
for right in range(len(nums)):
current_sum += nums[right]
while current_sum > limit:
current_sum -= nums[left]
left += 1
answer = max(answer, right - left + 1)
return answer이 코드에서 중요한 점은 left도 right도 뒤로 가지 않는다는 것입니다. 그래서 각 포인터가 배열을 한 번씩만 지나가며, 이런 유형은 보통 O(n)으로 처리됩니다.
인식 신호
- 배열이나 문자열에서 구간을 다룬다
- 두 수의 합, 차이, 거리 같은 관계를 본다
- 연속 부분 배열의 최대 길이 또는 최소 길이를 구한다
- 정렬하면 판단 규칙이 단순해진다
- 한쪽을 움직였을 때 버려도 되는 후보를 설명할 수 있다
실전에서는 정렬된 배열, 연속 부분 배열, 합이 K 이하, 가장 긴 구간 같은 표현이 보이면 투 포인터를 한 번 떠올려보면 좋습니다.
왜 이게 되는가
입문자에게 가장 중요한 질문은 이것입니다. 왜 포인터를 그렇게 움직여도 답을 놓치지 않을까? 정렬 배열에서는 순서가 보장되기 때문에 현재 합이 너무 크면 오른쪽을 줄여야 한다는 논리가 생깁니다. 연속 구간 문제에서는 윈도우 상태를 유지할 수 있기 때문에 오른쪽을 늘리고 필요하면 왼쪽을 줄여 다시 조건 안으로 들어올 수 있습니다.
즉, 투 포인터는 감으로 움직이는 기법이 아니라 문제 구조가 포인터 이동 규칙을 보장해주는 경우에만 안전한 기법입니다. 이 설명이 안 되면 아직 투 포인터로 확신하면 안 됩니다.
자주 하는 실수
- 정렬이 필요한데 그냥 양끝 포인터를 쓰는 실수
- 연속 구간 문제면 무조건 슬라이딩 윈도우라고 생각하는 실수
- 포인터 이동 이유를 설명하지 못한 채 코드만 외우는 실수
특히 음수가 섞인 구간 합 문제처럼 단순한 윈도우 규칙이 깨지는 경우도 있습니다. 그래서 조건이 단조롭게 유지되는지, 상태를 쉽게 갱신할 수 있는지를 먼저 확인해야 합니다.
시간복잡도
투 포인터가 자주 쓰이는 가장 큰 이유는 완전탐색의 O(n^2)를 O(n) 또는 O(n log n)까지 줄이는 경우가 많기 때문입니다. 하지만 무조건 선형 시간이라고 외우면 안 됩니다. 정렬이 필요할 수도 있고, 조건이 복잡하면 다른 자료구조가 더 필요할 수도 있습니다.
투 포인터의 핵심은 포인터 두 개 자체가 아니라, 각 포인터가 대체로 한 방향으로만 움직이면서 불필요한 후보를 버릴 수 있다는 점입니다.
한 번에 기억하는 기준
- 정렬된 배열에서 쌍을 찾는다 -> 양끝 투 포인터 의심
- 연속 부분 배열을 다룬다 -> 같은 방향 투 포인터 의심
- 모든 경우를 다 보면 O(n^2)다 -> 범위를 줄일 수 있는지 확인
- 한쪽을 움직여도 정답을 놓치지 않는 이유를 설명할 수 있어야 함
이 기준만 잡혀도 문제를 봤을 때 투 포인터를 떠올리는 속도가 훨씬 빨라집니다. 알고리즘 이름을 맞히는 것보다, 어떤 구조 때문에 범위를 줄일 수 있는지를 먼저 보는 습관이 더 중요합니다.
마무리
투 포인터 알고리즘은 특별한 공식 하나를 외우는 주제가 아닙니다. 오히려 문제를 보면서 여기서는 범위를 줄여도 되겠는데?라고 생각하는 감각에 더 가깝습니다. 그래서 완전탐색이 먼저 떠오르는 문제를 만났을 때는, 구현부터 하기 전에 정렬이나 구간 성질을 이용해 버릴 수 있는 후보가 없는지 먼저 확인해보면 좋습니다.
관련해서 탐색 사고법을 함께 보고 싶다면 BFS 알고리즘 기초 글, DFS 알고리즘 기초 글, 브루트포스, DFS, 백트래킹 비교 글도 함께 읽어보면 흐름이 더 잘 잡힙니다. 외부 참고 자료로는 USACO Guide의 Two Pointers 정리가 도움이 됩니다.
