투 포인터 알고리즘 (Two Pointer Algorithm)

개요

투 포인터(Two Pointer) 알고리즘은 두 개의 포인터를 이용하여 배열 또는 리스트를 탐색하는 기법입니다. 일반적으로 정렬된 배열에서 특정한 값을 찾거나, 부분 배열(서브 배열)의 특징을 확인할 때 사용됩니다.
이 알고리즘을 활용하면 O(N) 또는 O(N log N) 수준의 시간 복잡도로 문제를 해결할 수 있으며, 브루트 포스(Brute Force)보다 훨씬 효율적입니다.

---

투 포인터 알고리즘의 종류

1. 시작점-끝점 (Two Pointer for Interval)

✅ 연속된 구간(부분 배열, 서브 배열)을 탐색하는 경우
✅ 슬라이딩 윈도우(Sliding Window)와 함께 사용 가능
✅ 예제: 연속된 수들의 합이 특정 값을 만족하는 경우 찾기

2. 양 끝에서 중앙으로 (Two Pointer from Both Ends)

✅ 배열의 양 끝에서 중앙으로 이동하며 조건을 만족하는 경우 찾기
✅ 정렬된 배열에서 특정 값 찾기에 자주 사용
✅ 예제: 배열에서 두 수의 합이 특정 값을 만족하는 경우 찾기

---

1. 연속된 구간 탐색 (Two Pointer for Interval)

연속된 부분 배열(서브 배열)을 탐색할 때 사용되며, 슬라이딩 윈도우(Sliding Window) 방식과 유사합니다.

📌 예제: 연속된 부분 합 구하기

주어진 리스트에서 연속된 부분 배열의 합이 특정 값 X가 되는 경우의 수를 구하는 문제입니다.

def count_subarray_sum(arr, target):
    left, right, total, count = 0, 0, 0, 0
    n = len(arr)

    while right < n:
        total += arr[right]
        while total > target and left <= right:  # 부분 합이 target 초과면 left 이동
            total -= arr[left]
            left += 1
        if total == target:
            count += 1
        right += 1  # right 이동
    return count

arr = [1, 2, 3, 2, 5]
target = 5
print(count_subarray_sum(arr, target))  # 출력: 2

✅ 핵심 포인트

• left와 right 포인터를 이동시키면서 연속된 부분 배열의 합을 계산
• total이 목표 값을 초과하면 left 포인터를 오른쪽으로 이동
• total이 목표 값과 같으면 정답 카운트 증가

---

2. 양 끝에서 중앙으로 (Two Pointer from Both Ends)

배열의 양 끝에서 중앙으로 이동하면서 조건을 만족하는 요소를 찾는 방식입니다.
특히, 정렬된 배열에서 두 수의 합을 찾는 문제에 자주 사용됩니다.

📌 예제: 두 수의 합 찾기

정렬된 배열에서 두 수의 합이 특정 값 X가 되는 경우를 찾는 문제입니다.

def two_sum(arr, target):
    left, right = 0, len(arr) - 1  # 양 끝에서 시작

    while left < right:
        total = arr[left] + arr[right]
        if total == target:
            return (arr[left], arr[right])  # 정답 찾음
        elif total < target:
            left += 1  # 합이 작으면 left 증가
        else:
            right -= 1  # 합이 크면 right 감소
    return None  # 조건 만족하는 쌍이 없음

arr = [1, 2, 3, 4, 6, 8, 9]
target = 10
print(two_sum(arr, target))  # 출력: (2, 8)

✅ 핵심 포인트

• 정렬된 배열을 전제로 함
• left는 값이 너무 작으면 증가, right는 값이 너무 크면 감소
• O(N) 시간 복잡도로 해결 가능 (Brute Force 대비 개선됨)

---

3. 응용 문제

📌 3.1 가장 긴 연속 부분 배열 찾기

연속된 부분 배열의 합이 target 이하이면서 가장 긴 배열을 찾는 문제입니다.

def longest_subarray(arr, target):
    left, right, total, max_length = 0, 0, 0, 0
    n = len(arr)

    while right < n:
        total += arr[right]
        while total > target:
            total -= arr[left]
            left += 1
        max_length = max(max_length, right - left + 1)
        right += 1
    return max_length

arr = [1, 2, 3, 4, 5, 6, 7, 8]
target = 15
print(longest_subarray(arr, target))  # 출력: 5 (서브 배열: [1,2,3,4,5])

✅ 핵심 포인트

• left와 right를 조절하면서 조건을 만족하는 가장 긴 배열을 찾음
• 슬라이딩 윈도우 기법과 유사

---

📌 3.2 정렬된 배열에서 3개의 수의 합 찾기 (Three Sum)

투 포인터를 활용하여 3개의 숫자의 합이 0이 되는 조합 찾기 (LeetCode 15번)

def three_sum(nums):
    nums.sort()  # 정렬 필수
    result = []
    n = len(nums)

    for i in range(n - 2):
        if i > 0 and nums[i] == nums[i - 1]:  # 중복 방지
            continue
        left, right = i + 1, n - 1
        while left < right:
            total = nums[i] + nums[left] + nums[right]
            if total == 0:
                result.append([nums[i], nums[left], nums[right]])
                left += 1
                right -= 1
            elif total < 0:
                left += 1
            else:
                right -= 1
    return result

nums = [-1, 0, 1, 2, -1, -4]
print(three_sum(nums))  # 출력: [[-1, -1, 2], [-1, 0, 1]]

✅ 핵심 포인트

• 3중 루프 대신 투 포인터로 O(N²)으로 최적화
• 정렬 후, 고정된 첫 번째 값 + 투 포인터 활용

---

4. 투 포인터 알고리즘의 장단점

✅ 장점

• O(N) 또는 O(N log N) 수준의 빠른 탐색 가능
• 메모리 사용이 적음 (In-place 알고리즘)
• 브루트 포스(완전 탐색)보다 훨씬 효율적

❌ 단점

• 배열이 정렬되어 있어야 하는 경우가 많음
• 특정한 조건에서만 사용 가능 (예: 연속된 구간 탐색, 정렬된 배열)
• 변형 문제에서는 직관적인 구현이 어려울 수 있음

---

5. 결론

• 투 포인터 알고리즘은 효율적인 탐색을 위한 필수적인 기법
• 정렬된 배열에서 특정 조건을 만족하는 두 개 이상의 요소를 찾을 때 매우 효과적
• Sliding Window 기법과 결합하여 연속된 부분 배열 탐색에도 활용 가능

🚀 다양한 문제에서 활용할 수 있도록 연습해보세요!