투 포인터 | O(n²) → O(n) 최적화 기법 완벽 정리
이 글의 핵심
투 포인터: O(n²) → O(n) 최적화 기법 투 포인터 기본·실전 문제.
시리즈 안내
#16 | 📋 전체 목차 | 이전: #15 그리디 · 다음: #17 슬라이딩 윈도우
들어가며
”두 개의 포인터로 O(n²) → O(n)“
투 포인터는 두 개의 인덱스를 사용해서 배열을 효율적으로 탐색하는 기법입니다.
코딩 테스트 준비하며 깨달은 것
알고리즘 문제를 풀다 보면 “이게 실무에 무슨 도움이 될까?” 하는 의문이 들 때가 있습니다. 저도 그랬습니다. 하지만 실제 프로젝트에서 성능 문제에 부딪히면, 알고리즘 지식이 얼마나 중요한지 깨닫게 됩니다. 예를 들어, 사용자 검색 기능이 느려서 고민하다가 해시 테이블을 적용하니 응답 시간이 10초에서 0.1초로 줄어든 경험이 있습니다. 코딩 테스트는 단순히 취업을 위한 관문이 아니라, 문제 해결 능력을 키우는 훈련장입니다. 처음엔 브루트 포스로 풀다가, 시간 복잡도를 개선하는 과정에서 “아, 이렇게 생각하면 되는구나” 하는 깨달음을 얻을 때의 쾌감은 말로 표현하기 어렵습니다. 이 글에서는 단순히 정답 코드만 제시하는 게 아니라, 문제를 어떻게 접근하고 최적화하는지 사고 과정을 함께 공유하겠습니다.
1. 투 포인터 기본
패턴 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)패턴 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]2. 실전 문제
문제 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]]문제 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문제 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])3. 투 포인터 패턴
패턴 정리
# 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실전 팁
코딩 테스트 팁
# ✅ 정렬 여부 확인
# 정렬 안 되어 있으면 먼저 정렬
# ✅ 중복 처리
# 같은 값 스킵 로직 추가
# ✅ 경계 조건
# left < right, left <= right 주의정리
핵심 요약
- 투 포인터: 두 인덱스로 O(n) 탐색
- 패턴: 양 끝, 같은 방향, 구간 탐색
- 최적화: O(n²) → O(n)
- 정렬: 대부분 정렬 후 사용
추천 문제
백준
-
1806번: 부분합 프로그래머스
-
보석 쇼핑 LeetCode:
관련 글
자주 묻는 질문 (FAQ)
Q. 이 내용을 실무에서 언제 쓰나요?
A. 투 포인터: O(n²) → O(n) 최적화 기법 완벽 정리. 투 포인터 기본·실전 문제로 흐름을 잡고 원리·코드·실무 적용을 한글로 정리합니다. 알고리즘·투포인터·Two Pointers 중심으로 설명합니다.
Q. 선행으로 읽으면 좋은 글은?
A. 각 글 하단의 이전 글 또는 관련 글 링크를 따라가면 순서대로 배울 수 있습니다. C++ 시리즈 목차에서 전체 흐름을 확인할 수 있습니다.
Q. 더 깊이 공부하려면?
A. cppreference와 해당 라이브러리 공식 문서를 참고하세요. 글 말미의 참고 자료 링크도 활용하면 좋습니다.
같이 보면 좋은 글 (내부 링크)
이 주제와 연결되는 다른 글입니다.
이 글에서 다루는 키워드 (관련 검색어)
알고리즘, 투포인터, Two Pointers, 최적화, 코딩테스트 등으로 검색하시면 이 글이 도움이 됩니다.