투 포인터 알고리즘: O(N)으로 끝내는 배열 탐색 최적화

배열 내에서 특정한 조건을 만족하는 구간이나 쌍을 찾는 문제는 알고리즘 설계의 기본입니다. 가장 먼저 떠오르는 2중 루프 방식은 $O(N^2)$의 시간 복잡도를 가져 데이터가 조금만 커져도 처리 속도가 급격히 저하됩니다. 이때 마치 두 개의 바늘로 천을 훑고 지나가듯, 투 포인터(Two Pointers) 기법을 사용하면 선형 시간인 $O(N)$ 만에 문제를 해결할 수 있습니다. 본 포스팅에서는 투 포인터의 두 가지 주요 유형과 실제 문제 해결에서의 전략을 2,500자 이상의 밀도 있는 텍스트로 분석해 보겠습니다.

1. 투 포인터의 핵심 개념과 동작 방식

투 포인터는 배열이나 리스트에서 두 개의 지점(인덱스)을 가리키는 포인터를 조작하며 원하는 해를 찾는 기법입니다. 이 기법의 위력은 불필요한 탐색 범위를 과감히 건너뛰는 데 있습니다. 두 포인터의 이동 방향에 따라 크게 '같은 방향'으로 이동하는 방식과 '양 끝에서 시작하여 서로를 향해' 이동하는 방식으로 나뉩니다.

1-1. 같은 방향으로 이동하는 포인터 (Sliding Window 유사형)

주로 '특정한 합을 만족하는 연속 부분 수열'을 찾을 때 사용합니다. 시작점(Start)과 끝점(End) 포인터를 모두 첫 번째 인덱스에 두고, 현재 부분 합이 목표치보다 작으면 End를 밀어서 범위를 넓히고, 목표치보다 크면 Start를 밀어서 범위를 좁힙니다. 배열을 단 한 번만 훑기 때문에 연산 횟수가 획기적으로 줄어듭니다.

2. 정렬된 배열에서의 양 끝 포인터 전략

두 수의 합이 특정 값이 되는 쌍을 찾는 문제에서 배열이 정렬되어 있다면 양 끝 포인터 방식이 최적입니다. 왼쪽 포인터는 최소값에서, 오른쪽 포인터는 최대값에서 시작합니다. 두 수의 합이 목표보다 크면 오른쪽 포인터를 왼쪽으로 옮겨 합을 줄이고, 목표보다 작으면 왼쪽 포인터를 오른쪽으로 옮겨 합을 키웁니다. 이 논리적인 수렴 과정은 $O(N)$의 복잡도를 보장하며 완벽한 정답을 찾아냅니다.

2-1. 투 포인터의 정당성 증명

투 포인터가 왜 모든 경우를 다 보지 않고도 정답을 보장할까요? 이는 배열의 단조성(Monotonicity) 덕분입니다. 포인터를 이동시킴에 따라 구간의 합이나 원소의 크기가 일정하게 변하기 때문에, 현재 상태에서 더 이상 탐색할 필요가 없는 범위를 수학적으로 확신하고 배제할 수 있는 것입니다.

3. 투 포인터와 브루트 포스의 성능 비교

데이터 개수가 10만 개($10^5$)일 때, $O(N^2)$ 알고리즘은 100억 번의 연산이 필요하여 일반적인 컴퓨터에서 100초 이상의 시간이 걸립니다. 반면 투 포인터의 $O(N)$ 알고리즘은 단 0.001초 내외로 처리가 완료됩니다. 이러한 압도적인 차이는 실시간 트래픽을 처리하는 검색 엔진이나 추천 알고리즘에서 투 포인터가 선택되는 결정적인 이유가 됩니다.

투 포인터 활용의 대표 사례

연속 부분 수열의 합: 특정 합 $M$을 가지는 연속적인 구간의 개수 찾기.
두 수의 합 문제: 정렬된 수열에서 합이 $X$가 되는 두 원소의 쌍 찾기.
중복 원소 제거: 정렬된 배열에서 중복을 건너뛰며 유니크한 값들만 추출하기.
팰린드롬 검사: 문자열의 양 끝에서 중앙으로 좁혀오며 대칭 여부 판단하기.


# 특정한 합 M을 가진 연속 부분 수열 찾기 (Python)
def count_subarrays_with_sum(arr, m):
    count = 0
    current_sum = 0
    end = 0
    
    for start in range(len(arr)):
        # end를 가능한 만큼 오른쪽으로 이동
        while current_sum < m and end < len(arr):
            current_sum += arr[end]
            end += 1
        
        # 부분합이 m과 같다면 카운트 증가
        if current_sum == m:
            count += 1
        
        # 다음 루프 전 start를 이동시키므로 현재 start 원소를 차감
        current_sum -= arr[start]
    return count

[투 포인터 핵심 요약]
1. 전략: 두 개의 인덱스 변수를 활용해 배열을 단 한 번만 순회하며 정답을 찾습니다.
2. 효율: 2중 루프($O(N^2)$)의 연산량을 선형 시간($O(N)$)으로 획기적으로 개선합니다.
3. 조건: 배열의 요소가 정렬되어 있거나 구간의 변화가 단조로울 때 가장 강력한 위력을 발휘합니다.

tech-korea