투 포인터는 언제 쓰나요?

정렬된 배열에서 두 수의 합, 부분 배열 찾기 등에 사용. O(n²) → O(n) 최적화.

슬라이딩 윈도우와 차이는?

투 포인터는 조건에 따라 이동, 슬라이딩 윈도우는 고정 크기 이동.

정렬 안 된 배열에서도 되나요?

가능하지만 대부분 정렬 후 사용합니다. 정렬 비용 O(n log n).

투 포인터 | O(n²) → O(n) 최적화 기법 완벽 정리

2026년 3월 28일 · 22분 읽기 · 수정 2026년 3월 30일 중급 튜토리얼

이 글의 핵심

투 포인터에 대한 실전 가이드입니다. O(n²) → O(n) 최적화 기법 완벽 정리 등을 예제와 함께 상세히 설명합니다.

들어가며

”두 개의 포인터로 O(n²) → O(n)”

투 포인터는 두 개의 인덱스를 사용해서 배열을 효율적으로 탐색하는 기법입니다.

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)
정렬: 대부분 정렬 후 사용