투 포인터: O(n²) 탐색을 O(n)으로 줄이는 조건과 대표 문제
이 글의 핵심
투 포인터는 정렬되어 있거나 포인터를 움직일 때 조건이 한 방향으로만 변하는 경우에만 통합니다. 이 전제를 먼저 짚고 대표 문제에 적용해 본 뒤, 세 수의 합에서 같은 조합이 중복으로 나오지 않게 건너뛰는 처리와 코딩 테스트에서 패턴을 알아보는 요령을 정리합니다.
시리즈 안내
#16 | 📋 전체 목차 | 이전: #15 그리디 · 다음: #17 슬라이딩 윈도우
들어가며
투 포인터는 두 개의 인덱스를 사용해서 배열을 효율적으로 탐색하는 기법입니다.
이중 루프로 모든 쌍 (i, j)를 검사하면 n개 원소에서 약 n²/2번 비교해야 합니다. 투 포인터는 이 쌍들 중 “답이 될 수 없다”는 것이 확실한 쌍을 한꺼번에 버리면서 진행합니다. 핵심은 포인터가 되돌아가지 않는다는 점입니다. 두 포인터가 각각 최대 n번만 움직이므로 전체 이동 횟수가 2n 이하가 되고, 그래서 O(n)입니다.
이 “한꺼번에 버리기”가 정당하려면 조건이 필요합니다. 포인터를 한 방향으로 움직였을 때 관심 있는 값(합, 구간 길이 등)이 단조롭게 변해야 합니다. 정렬된 배열에서 왼쪽 포인터를 오른쪽으로 옮기면 합은 커지기만 하고, 오른쪽 포인터를 왼쪽으로 옮기면 작아지기만 합니다. 양수만 있는 배열에서 구간을 넓히면 합이 커지기만 합니다. 이런 단조성이 없으면 투 포인터로 짠 코드는 답을 건너뛰고 틀린 결과를 내는데, 에러도 없이 일부 테스트만 통과하기 때문에 원인을 찾기가 어렵습니다.
투 포인터 기본
패턴 1: 양 끝에서 시작
def two_sum_sorted(arr, target):
"""
정렬된 배열에서 두 수의 합이 target
"""
left, right = 0, len(arr) - 1
while left < right:
current_sum = arr[left] + arr[right]
if current_sum == target:
return [left, right]
elif current_sum < target:
left += 1 # 합을 키움
else:
right -= 1 # 합을 줄임
return []
# 테스트
arr = [1, 2, 3, 4, 6]
print(two_sum_sorted(arr, 6)) # [1, 3] (2+4=6)왜 current_sum < target일 때 left를 옮겨도 되는지가 이 패턴의 전부입니다. 지금 arr[left] + arr[right]가 target보다 작다면, arr[left]와 짝지을 수 있는 가장 큰 값인 arr[right]와 더해도 부족하다는 뜻입니다. 그러면 arr[left]는 left+1 ... right-1 중 누구와 짝지어도 target에 못 미치므로, 이 원소를 포함하는 모든 쌍을 한 번에 후보에서 지울 수 있습니다. 합이 클 때 right를 줄이는 것도 같은 논리의 대칭입니다. 한 번의 비교로 한 줄(행 또는 열)의 쌍 전체를 제거하므로 O(n)이 됩니다.
이 방식은 정렬된 입력을 전제로 합니다. LeetCode 1번 “Two Sum”처럼 정렬되지 않은 배열에서 원래 인덱스를 돌려줘야 하는 문제에 정렬 후 투 포인터를 적용하면, 정렬 과정에서 인덱스가 바뀌어 오답이 됩니다. 이런 경우에는 해시 테이블로 “지금까지 본 값 → 인덱스”를 저장하는 O(n) 풀이가 더 적합합니다. 정렬이 허용된다면 투 포인터는 추가 메모리가 O(1)이라는 장점이 있습니다.
패턴 2: 같은 방향 이동
def remove_duplicates(arr):
"""
정렬된 배열에서 중복 제거 (in-place)
"""
if not arr:
return 0
write = 1 # 쓰기 포인터
for read in range(1, len(arr)): # 읽기 포인터
if arr[read] != arr[read - 1]:
arr[write] = arr[read]
write += 1
return write
# 테스트
arr = [1, 1, 2, 2, 3, 4, 4]
length = remove_duplicates(arr)
print(arr[:length]) # [1, 2, 3, 4]같은 방향 패턴에서 read는 모든 원소를 한 번씩 훑고, write는 “지금까지 확정된 결과의 끝”을 가리킵니다. write는 항상 read보다 앞서지 않으므로, 아직 읽지 않은 원소를 덮어쓸 위험이 없습니다. 이것이 새 배열 없이 제자리(in-place)로 처리할 수 있는 이유입니다. 정렬되어 있어야 하는 이유도 분명합니다. 같은 값이 연속으로 붙어 있어야 arr[read - 1]과만 비교해도 중복을 판단할 수 있습니다.
함수가 배열 자체를 줄이지 않고 새 길이만 돌려준다는 점에 주의해야 합니다. arr 뒤쪽에는 [1, 2, 3, 4, 3, 4, 4]처럼 이전 값이 그대로 남아 있습니다. 호출하는 쪽이 반환값을 무시하고 arr 전체를 쓰면 쓰레기 값이 섞입니다. Python이라면 del arr[length:]로 잘라 주는 것이 명확합니다. 이 read/write 구조는 “0을 배열 끝으로 옮기기”, “특정 값 제거” 같은 문제에도 비교 조건만 바꿔 그대로 쓰입니다.
같은 방향 패턴의 또 다른 형태는 속도가 다른 두 포인터입니다. 연결 리스트에서 slow는 한 칸, fast는 두 칸씩 움직이면 fast가 끝에 닿을 때 slow는 정확히 중간에 있고, 리스트에 사이클이 있으면 두 포인터가 언젠가 반드시 만납니다(Floyd의 사이클 탐지). 인덱스로 임의 접근이 안 되는 연결 리스트에서 길이를 미리 세지 않고 한 번의 순회로 중간이나 사이클을 찾을 수 있다는 점이 이 기법의 가치입니다. fast를 두 칸 옮기기 전에 fast와 fast.next가 모두 None이 아닌지 확인하지 않으면 AttributeError: 'NoneType' object has no attribute 'next'가 나는데, 이 경계 검사를 빠뜨리는 것이 가장 흔한 실수입니다.
실전 문제
문제 1: 세 수의 합
def three_sum(arr):
"""
합이 0인 세 수 찾기
[-1, 0, 1, 2, -1, -4] → [[-1, -1, 2], [-1, 0, 1]]
"""
arr.sort()
result = []
for i in range(len(arr) - 2):
# 중복 스킵
if i > 0 and arr[i] == arr[i - 1]:
continue
left, right = i + 1, len(arr) - 1
while left < right:
total = arr[i] + arr[left] + arr[right]
if total == 0:
result.append([arr[i], arr[left], arr[right]])
# 중복 스킵
while left < right and arr[left] == arr[left + 1]:
left += 1
while left < right and arr[right] == arr[right - 1]:
right -= 1
left += 1
right -= 1
elif total < 0:
left += 1
else:
right -= 1
return result
# 테스트
arr = [-1, 0, 1, 2, -1, -4]
print(three_sum(arr))
# [[-1, -1, 2], [-1, 0, 1]]세 수의 합은 “하나를 고정하고 나머지 둘은 패턴 1로 찾는다”로 분해합니다. 바깥 루프가 n번, 안쪽 투 포인터가 O(n)이므로 전체는 O(n²)입니다. 모든 세 쌍을 검사하는 O(n³)보다 한 차수 낮고, 정렬 비용 O(n log n)은 여기에 흡수됩니다.
이 문제에서 가장 많이 틀리는 곳은 중복 처리입니다. 제가 이 문제를 처음 풀 때도 정답 개수는 맞는데 [-1, 0, 1]이 두 번 들어가서 오답 처리됐습니다. 정렬 후 -1이 두 개 있으면 두 -1을 각각 기준으로 같은 조합을 한 번씩 찾기 때문입니다. 그래서 스킵 로직이 두 군데에 필요합니다. 기준 i는 바로 앞 원소와 같으면 건너뜁니다(arr[i] == arr[i + 1]로 비교하면 [-1, -1, 2]처럼 같은 값을 두 번 쓰는 조합을 놓칩니다). 답을 찾은 뒤에는 left와 right를 같은 값이 끝날 때까지 밀고 나서 한 칸 더 움직입니다. 답을 찾지 못한 경우에는 스킵이 필요 없습니다. 같은 값이 여러 번 검사되더라도 결과에 추가되지는 않기 때문입니다.
결과를 set에 튜플로 넣어 나중에 중복을 제거해도 정답은 나오지만, 중복 조합이 많은 입력(예: 0이 수천 개)에서는 같은 조합을 반복해서 만들고 해싱하느라 시간 초과가 나기 쉽습니다. 추가로 arr[i] > 0이면 이후 원소도 모두 양수라 합이 0이 될 수 없으므로 루프를 break하는 가지치기를 넣으면 실행 시간이 눈에 띄게 줄어듭니다.
문제 2: 컨테이너 물 담기
def max_area(heights):
"""
두 선 사이에 담을 수 있는 최대 물의 양
"""
left, right = 0, len(heights) - 1
max_water = 0
while left < right:
width = right - left
height = min(heights[left], heights[right])
water = width * height
max_water = max(max_water, water)
# 낮은 쪽 이동
if heights[left] < heights[right]:
left += 1
else:
right -= 1
return max_water
# 테스트
heights = [1, 8, 6, 2, 5, 4, 8, 3, 7]
print(max_area(heights)) # 49이 문제는 배열이 정렬되어 있지 않은데도 투 포인터가 통하는 예입니다. 단조성이 값이 아니라 폭에서 나오기 때문입니다. 양 끝에서 시작하면 폭은 최대이고, 포인터를 움직일 때마다 폭은 1씩 줄어듭니다. 물의 양은 폭 × 낮은 쪽 높이인데, 높은 쪽 포인터를 안으로 옮기면 폭은 줄고 높이는 여전히 낮은 쪽에 묶여 있어 결코 늘어날 수 없습니다. 따라서 낮은 쪽 막대를 포함한 나머지 쌍은 모두 현재 값 이하이므로, 낮은 쪽을 버리는 것이 안전합니다.
“높은 쪽을 옮기면 더 높은 막대를 만날 수도 있지 않나?”라는 의문이 자주 나오는데, 높은 막대를 만나도 높이는 min으로 낮은 쪽에 제한되므로 이득이 없습니다. 두 높이가 같을 때는 어느 쪽을 옮겨도 정답에 영향이 없습니다. 둘 중 하나를 옮겨서 나오는 모든 쌍이 현재 높이 이하로 제한되기 때문입니다. 이 증명을 이해하지 못하고 외우기만 하면, 비슷해 보이지만 단조성이 없는 “빗물 가두기(Trapping Rain Water)” 같은 문제에 같은 코드를 잘못 적용하게 됩니다.
문제 3: 부분 배열 합
def subarray_sum(arr, target):
"""
연속된 부분 배열의 합이 target (양수 배열)
"""
left = 0
current_sum = 0
count = 0
for right in range(len(arr)):
current_sum += arr[right]
# 합이 target보다 크면 left 이동
while current_sum > target and left <= right:
current_sum -= arr[left]
left += 1
if current_sum == target:
count += 1
return count
# 테스트
arr = [1, 2, 3, 4, 5]
print(subarray_sum(arr, 5)) # 2 ([2,3], [5])right가 구간을 넓히고, 합이 너무 커지면 left가 구간을 줄이는 구조입니다. while 루프가 안에 있어 O(n²)처럼 보이지만, left는 전체 실행 동안 최대 n번만 증가하므로 분할상환하면 O(n)입니다.
docstring의 “양수 배열” 조건이 이 코드의 정확성을 떠받칩니다. 모든 원소가 양수여야 “구간을 늘리면 합이 커지고, 줄이면 작아진다”는 단조성이 성립합니다. 음수가 섞이면 합이 target을 넘었다고 해서 left를 옮기는 것이 정당하지 않습니다(뒤에 음수가 와서 다시 줄어들 수 있음). 0이 섞여도 문제가 생깁니다. [0, 5]에서 target 5인 구간은 [0, 5]와 [5] 두 개인데, 이 코드는 left를 0에 둔 채 한 번만 세서 1을 돌려줍니다. 음수나 0이 있는 입력에서 개수를 세야 한다면 누적합과 해시맵(prefix_sum - target의 등장 횟수를 세는 방식)을 쓰는 것이 정석이며, LeetCode 560번 “Subarray Sum Equals K”가 바로 그 경우입니다.
투 포인터 패턴
패턴 정리
# 1. 양 끝에서 시작 (정렬 필수)
left, right = 0, len(arr) - 1
while left < right:
# 조건에 따라 left++ 또는 right--
# 2. 같은 방향 (fast & slow)
slow = 0
for fast in range(len(arr)):
# 조건 만족 시 slow++
# 3. 구간 탐색
left = 0
for right in range(len(arr)):
# 구간 [left, right] 처리
while 조건:
left += 1세 패턴을 구분하는 기준은 포인터가 표현하는 의미입니다. 양 끝 패턴의 두 포인터는 “짝을 이룰 두 원소”이고, 같은 방향 패턴은 “읽는 위치와 쓰는 위치”, 구간 탐색 패턴은 “구간의 시작과 끝”입니다. 1번 패턴의 주석 “정렬 필수”는 정확히는 “값을 기준으로 판단할 때 정렬 필수”이며, 컨테이너 물 담기처럼 폭이 단조성을 제공하는 경우는 예외입니다.
3번 구간 탐색은 다음 글에서 다룰 슬라이딩 윈도우와 사실상 같은 구조입니다. 흔히 “고정 크기면 슬라이딩 윈도우, 가변이면 투 포인터”라고 구분하지만, 가변 크기 윈도우도 슬라이딩 윈도우라고 부르는 경우가 많아서 이름보다 “포인터가 되돌아가지 않는가”라는 본질을 기준으로 이해하는 편이 좋습니다.
정렬 여부와 경계 조건 정하기
# ✅ 정렬 여부 확인
# 정렬 안 되어 있으면 먼저 정렬
# ✅ 중복 처리
# 같은 값 스킵 로직 추가
# ✅ 경계 조건
# left < right, left <= right 주의“정렬 안 되어 있으면 먼저 정렬”은 문제가 원래 인덱스를 요구하지 않을 때만 해당합니다. 인덱스가 필요하다면 (값, 원래 인덱스) 쌍으로 정렬하거나 해시 기반 풀이로 바꿔야 합니다.
경계 조건은 포인터가 가리키는 대상에 따라 결정됩니다. 서로 다른 두 원소를 짝짓는 양 끝 패턴은 같은 원소를 두 번 쓰면 안 되므로 left < right입니다. 구간 탐색에서 left <= right는 “구간이 원소 하나일 때까지 줄일 수 있다”는 뜻이며, 부분 배열 합 예제처럼 left가 right + 1까지 가서 빈 구간이 되는 것을 허용할지도 문제에 따라 정해야 합니다. 저는 이런 조건을 헷갈릴 때 원소 1개, 2개짜리 배열과 모든 원소가 같은 배열을 손으로 돌려 보는데, 투 포인터 버그의 대부분이 이 세 가지 입력에서 드러납니다.
문제에서 투 포인터를 떠올리는 신호도 기억해 두면 좋습니다. 입력 크기가 10⁵ 이상이라 O(n²)이 불가능하고, “연속된 부분 배열”, “두 수의 합/차”, “정렬된 배열”, “제자리(in-place)로” 같은 표현이 나오면 투 포인터를 먼저 검토해 볼 만합니다.
추천 문제
투 포인터가 통하려면 포인터를 한 방향으로 움직일 때 판단 기준이 단조롭게 변해야 합니다. 구간 합 문제에 음수가 섞여 있으면 오른쪽을 늘려도 합이 줄어들 수 있어서 이 전제가 깨지므로, 그때는 누적 합과 해시를 쓰는 방식으로 바꿔야 합니다.
백준:
프로그래머스:
LeetCode:
백준 2003번은 문제 3의 코드를 거의 그대로 적용할 수 있고, 1806번은 “합이 S 이상인 가장 짧은 구간”을 찾는 변형이라 while 조건을 >=로 바꾸고 줄이는 동안 길이를 갱신하면 됩니다. 보석 쇼핑은 구간 안의 원소 종류를 해시맵으로 세면서 투 포인터를 움직이는 문제라 다음 글의 슬라이딩 윈도우와 연결됩니다.
같이 보면 좋은 글
자주 묻는 질문 (FAQ)
Q. 세 수의 합에서 같은 조합이 여러 번 나오지 않게 하려면 어떻게 하나요?
A. 먼저 배열을 정렬한 뒤, 기준 원소 i가 바로 앞 원소와 같으면 건너뛰어 같은 기준으로 다시 탐색하지 않게 합니다. 합이 0인 조합을 찾은 뒤에도 left와 right가 같은 값 위에 있는 동안 계속 이동시켜 중복 쌍을 건너뜁니다. 결과를 set에 넣어 나중에 중복을 제거하는 방법도 있지만, 정렬 상태를 활용해 탐색 중에 건너뛰는 편이 메모리와 시간 모두 유리합니다.