[2026] 투 포인터 | O(n²) → O(n) 최적화 기법 완벽 정리
![[2026] 투 포인터 | O(n²) → O(n) 최적화 기법 완벽 정리](/og/s/algorithm-series-16-two-pointers.webp)
이 글의 핵심
투 포인터: O(n²) → O(n) 최적화 기법 투 포인터 기본·실전 문제.
들어가며
”두 개의 포인터로 O(n²) → O(n)“
투 포인터는 두 개의 인덱스를 사용해서 배열을 효율적으로 탐색하는 기법입니다.
코딩 테스트 준비하며 깨달은 것
알고리즘 문제를 풀다 보면 “이게 실무에 무슨 도움이 될까?” 하는 의문이 들 때가 있습니다. 저도 그랬습니다. 하지만 실제 프로젝트에서 성능 문제에 부딪히면, 알고리즘 지식이 얼마나 중요한지 깨닫게 됩니다. 예를 들어, 사용자 검색 기능이 느려서 고민하다가 해시 테이블을 적용하니 응답 시간이 10초에서 0.1초로 줄어든 경험이 있습니다. 코딩 테스트는 단순히 취업을 위한 관문이 아니라, 문제 해결 능력을 키우는 훈련장입니다. 처음엔 브루트 포스로 풀다가, 시간 복잡도를 개선하는 과정에서 “아, 이렇게 생각하면 되는구나” 하는 깨달음을 얻을 때의 쾌감은 말로 표현하기 어렵습니다. 이 글에서는 단순히 정답 코드만 제시하는 게 아니라, 문제를 어떻게 접근하고 최적화하는지 사고 과정을 함께 공유하겠습니다.
1. 투 포인터 기본
패턴 1: 양 끝에서 시작
다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
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)패턴 2: 같은 방향 이동
다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
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]2. 실전 문제
문제 1: 세 수의 합
다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
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]]문제 2: 컨테이너 물 담기
다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
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문제 3: 부분 배열 합
다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
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])3. 투 포인터 패턴
패턴 정리
다음은 python를 활용한 상세한 구현 코드입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
# 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실전 팁
코딩 테스트 팁
아래 코드는 python를 사용한 구현 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.
# ✅ 정렬 여부 확인
# 정렬 안 되어 있으면 먼저 정렬
# ✅ 중복 처리
# 같은 값 스킵 로직 추가
# ✅ 경계 조건
# left < right, left <= right 주의정리
핵심 요약
- 투 포인터: 두 인덱스로 O(n) 탐색
- 패턴: 양 끝, 같은 방향, 구간 탐색
- 최적화: O(n²) → O(n)
- 정렬: 대부분 정렬 후 사용
추천 문제
백준:
- 2003번: 수들의 합 2
- 1806번: 부분합 프로그래머스:
- 보석 쇼핑 LeetCode:
- 15. 3Sum
- 11. Container With Most Water