투 포인터(Two Pointers) 알고리즘 (원리, 예제)

알고리즘 코딩 테스트나 실무에서 대용량 데이터를 처리할 때, 가장 빈번하게 마주치는 성능 저하의 원인은 이중 반복문(Nested Loop)입니다. $N$개의 데이터에 대해 $O(N^2)$의 시간 복잡도를 가지는 코드는 데이터가 10만 개만 넘어가도 수백억 번의 연산을 수행하게 되어 '시간 초과(Time Limit Exceeded)' 판정을 받게 됩니다. 이러한 비효율적인 탐색 로직을 획기적으로 개선하여 선형 시간(O(N)) 내에 문제를 해결할 수 있도록 돕는 강력한 기법이 바로 투 포인터(Two Pointers) 알고리즘입니다. 이 글에서는 투 포인터의 작동 원리와 대표적인 유형, 그리고 실제 코드 구현을 통해 그 효율성을 입증해 보겠습니다.

1. 투 포인터(Two Pointers)의 핵심 원리

투 포인터 알고리즘은 이름 그대로 두 개의 점(포인터)을 사용하여 배열이나 리스트와 같은 선형 자료구조를 탐색하는 기법입니다. 일반적으로 배열의 인덱스를 가리키는 두 개의 변수를 조작하여, 불필요한 탐색 범위를 동적으로 줄여나가는 것이 핵심입니다.

1-1. 왜 사용하는가? (시간 복잡도 최적화)

특정 조건을 만족하는 부분 배열을 찾거나, 두 수의 합을 구하는 문제에서 모든 경우의 수를 확인하는 '브루트 포스(Brute Force)' 방식은 $O(N^2)$의 시간이 소요됩니다. 반면, 투 포인터는 데이터를 단 한 번만 순회(Scan)하기 때문에 시간 복잡도를 $O(N)$으로 단축시킬 수 있습니다. 이는 데이터가 클수록 압도적인 성능 차이를 만듭니다.

2. 투 포인터의 두 가지 대표 유형

포인터가 움직이는 방향에 따라 크게 두 가지 패턴으로 나뉩니다. 문제의 성격에 따라 적절한 방식을 선택해야 합니다.

2-1. 양방향 (Bi-directional) : 시작과 끝에서 만나는 구조

주로 정렬된 배열에서 두 수의 합(Two Sum)을 찾거나 회문(Palindrome)을 판별할 때 사용됩니다.

초기화: 왼쪽 포인터(Left)는 0, 오른쪽 포인터(Right)는 $N-1$에서 시작합니다.
이동: 두 포인터가 서로를 향해 좁혀오며, 조건에 따라 Left를 증가시키거나 Right를 감소시킵니다.
종료: Left와 Right가 만나거나 교차하면(`Left >= Right`) 탐색을 종료합니다.

2-2. 단방향 (Equi-directional) : 슬라이딩 윈도우와 유사

특정 구간의 합이나 연속된 부분 수열을 찾을 때 사용됩니다.

초기화: 두 포인터(Start, End) 모두 0에서 시작합니다.
이동: 한 포인터(End)가 범위를 확장하고, 다른 포인터(Start)가 뒤따라가며 범위를 축소하는 방식입니다.

3. 실전 예제: 정렬된 배열에서 두 수의 합 찾기

가장 클래식한 문제인 "오름차순으로 정렬된 수열에서 두 수의 합이 타겟(Target) 값이 되는 경우"를 해결해 보겠습니다.

3-1. 알고리즘 로직

배열의 양 끝에 포인터를 둡니다. (`left=0`, `right=len-1`)
두 포인터가 가리키는 값의 합(`sum`)을 계산합니다.
Case A: `sum == target` 이면 정답을 찾은 것입니다.
Case B: `sum < target` 이면 합을 키워야 하므로, 작은 값을 가리키는 `left`를 오른쪽으로 1칸 이동합니다.
Case C: `sum > target` 이면 합을 줄여야 하므로, 큰 값을 가리키는 `right`를 왼쪽으로 1칸 이동합니다.

4. 파이썬(Python) 코드 구현

다음은 위 로직을 코드로 구현한 예시입니다. 정렬된 상태를 가정하므로 별도의 정렬 과정(`sort`)은 생략되어 있거나 전처리로 필요합니다.


def two_sum_sorted(nums, target):
    left = 0
    right = len(nums) - 1
    
    while left < right:
        current_sum = nums[left] + nums[right]
        
        if current_sum == target:
            return f"Found: index {left}({nums[left]}) and {right}({nums[right]})"
        
        elif current_sum < target:
            # 합이 부족하므로 더 큰 값을 더하기 위해 left 이동
            left += 1
            
        else:
            # 합이 넘치므로 더 작은 값을 더하기 위해 right 이동
            right -= 1
            
    return "Not Found"

# 테스트
data = [1, 3, 5, 7, 9, 11, 15]
target_value = 12

print(two_sum_sorted(data, target_value))
# 출력: Found: index 1(3) and 4(9)

[핵심 요약 : 투 포인터 알고리즘]
1. 성능 개선: 이중 루프의 $O(N^2)$ 복잡도를 $O(N)$으로 최적화하는 강력한 도구입니다.
2. 전제 조건: 양방향 투 포인터를 사용하려면 데이터가 반드시 정렬(Sorted)되어 있어야 합니다.
3. 활용: 두 수의 합(Two Sum), 부분 배열의 합, 회문 판별 등 연속적인 데이터 탐색에 필수적입니다.

kguidebook0001 님의 블로그