투 포인터(Two Pointer)는 배열이나 문자열에서 두 개의 포인터를 사용해 구간을 좁혀가는 알고리즘 기법이다. 특정 조건을 만족하는 쌍이나 부분 배열을 O(n)에 찾을 수 있다.
패턴 1: 두 끝에서 좁히기
python
# 정렬된 배열에서 합이 target인 두 수 찾기
def two_sum_sorted(arr, target):
left, right = 0, len(arr) - 1
while left < right:
s = arr[left] + arr[right]
if s == target:
return (arr[left], arr[right])
elif s < target:
left += 1
else:
right -= 1
return None
arr = [1, 2, 4, 6, 8, 9]
print(two_sum_sorted(arr, 10)) # (2, 8)
패턴 2: 같은 방향으로 이동
python
# 정렬된 배열에서 중복 제거 (in-place)
def remove_duplicates(nums):
if not nums: return 0
slow = 0
for fast in range(1, len(nums)):
if nums[fast] != nums[slow]:
slow += 1
nums[slow] = nums[fast]
return slow + 1
패턴 3: 회문 검사
python
def is_palindrome(s):
left, right = 0, len(s) - 1
while left < right:
if s[left] != s[right]:
return False
left += 1; right -= 1
return True
관련 개념
참고문헌
- •LeetCode Two Pointer 문제 모음
