[Python] 투 포인터(Two Pointer)

핵심 개념

투 포인터(Two Pointer)는 배열이나 리스트에서 두 개의 포인터를 활용해 문제를 해결하는 기법이다. 주로 정렬된 배열에서 특정 조건을 만족하는 부분을 찾거나, 두 개의 배열을 병합할 때 사용된다. 탐색 범위를 줄여 효율적으로 동작하기 때문에 많은 알고리즘 문제에서 활용된다.

 

시간 복잡도

Two Pointer 기법의 시간 복잡도는 일반적으로 \( O(N) \)이다. 각 포인터가 배열을 한 번씩만 훑고 지나가기 때문에 불필요한 중복 연산이 줄어든다. 반면, Brute Force 접근법은 \( O(N^2) \)인 경우가 많아 투 포인터를 사용하면 성능을 크게 향상시킬 수 있다.

 

동작방식 & 구현

Fig 1. Two Pointer

 

투 포인터는 보통 다음과 같은 방식으로 동작한다.

1. 시작점과 끝점을 설정: 두 개의 포인터를 배열의 시작과 끝 또는 특정 기준에 맞게 배치한다.
2. 조건에 따라 이동: 특정 조건을 만족할 때까지 포인터를 이동시키며 탐색한다.
3. 결과 도출: 문제에서 요구하는 조건을 만족하는 경우 값을 저장하거나 연산을 수행한다.

 

활용 가능한 문제 유형

• 합이 특정 값이 되는 두 수 찾기: 위의 예제처럼 두 개의 요소 합이 특정 값을 만족하는지 찾는 문제
• 구간 합(연속된 부분 배열의 합 찾기): 특정 조건을 만족하는 연속된 부분 배열의 합을 찾는 문제
• 두 개의 정렬된 배열 병합(Merge): 정렬된 두 개의 배열을 하나로 합치는 과정에서 효율적으로 사용됨
• 팰린드롬 검사: 문자열이 팰린드롬인지 검사할 때, 양쪽에서 포인터를 이동시키며 비교하는 방식으로 활용 가능
• 투 포인터 + 슬라이딩 윈도우: 투 포인터를 활용하여 가변 길이의 윈도우를 이동시키며 문제 해결

 

예제 코드(Python)

def two_sum(arr, target):
    arr.sort()  # 정렬된 상태에서 투 포인터 사용
    left, right = 0, len(arr) - 1
    
    while left < right:
        current_sum = arr[left] + arr[right]
        if current_sum == target:
            return (arr[left], arr[right])
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    
    return None

# 예제 실행
arr = [1, 3, 5, 7, 9]
target = 10
print(two_sum(arr, target))  # 출력: (1, 9)

 

결론

투 포인터는 배열 탐색을 최적화할 수 있는 강력한 알고리즘 기법이다. 단순한 브루트포스 방식보다 시간 복잡도를 개선할 수 있으며, 특정 문제 유형에서는 가장 효율적인 해결책이 될 수 있다. 문제 유형에 따라 투 포인터를 적절히 적용하면 훨씬 빠르고 효율적인 코드를 작성할 수 있다.

 

---

 

참고 자료

 

https://medium.com/@lucien1999s.pro/two-pointer-a1dd79fefd1a