Two Pointer (투 포인터)

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

Two Pointer(투 포인터) 알고리즘은 배열이나 리스트에서 두 개의 포인터를 사용하여 문제를 해결하는 기법입니다.
이 방법은 정렬된 배열, 부분 배열, 두 배열 간의 비교 문제에서 자주 활용됩니다.

 

활용 예시:

• 배열 내에서 특정 조건을 만족하는 두 개의 값 찾기
• 부분 배열의 특정 조건 만족 여부 판단
• 두 개의 정렬된 리스트 병합 또는 비교

투포인터

 

1️⃣ Two Pointer 기법이 필요한 이유

일반적으로 브루트 포스(완전 탐색) 를 사용하면 시간 복잡도가 높아지기 때문에 효율적인 탐색 방법이 필요합니다.
Two Pointer를 사용하면 불필요한 탐색을 줄이고 O(N) 또는 O(N log N) 시간 복잡도로 최적화할 수 있습니다.

✔ Two Pointer의 핵심 아이디어

1. 두 개의 포인터를 사용하여 탐색 (보통 시작과 끝에서 시작)
2. 조건을 만족하면 포인터 이동 (필요에 따라 한쪽 포인터만 이동하거나, 두 개가 동시에 이동)
3. 불필요한 탐색을 줄여 시간 복잡도를 줄임

---

2️⃣ 배열에서 특정 합을 만족하는 두 수 찾기 (O(N))

🔹 문제: 정렬된 배열에서 두 수의 합이 target이 되는 경우 찾기

✔ Brute Force (완전 탐색, O(N²))

def find_pair_brute_force(arr, target):
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            if arr[i] + arr[j] == target:
                return (arr[i], arr[j])
    return None

arr = [1, 2, 3, 4, 6]
target = 6
print(find_pair_brute_force(arr, target))  # (2, 4)

✔ Two Pointer (O(N))

def find_pair_two_pointer(arr, target):
    left, right = 0, len(arr) - 1
    
    while left < right:
        curr_sum = arr[left] + arr[right]
        if curr_sum == target:
            return (arr[left], arr[right])
        elif curr_sum < target:
            left += 1  # 합이 작으면 왼쪽 포인터 증가
        else:
            right -= 1  # 합이 크면 오른쪽 포인터 감소
    
    return None

arr = [1, 2, 3, 4, 6]
target = 6
print(find_pair_two_pointer(arr, target))  # (2, 4)

📌 완전 탐색은 모든 조합을 검사하지만, Two Pointer는 한 번만 순회하며 효율적으로 탐색 가능!

---

3️⃣ 부분 배열의 합이 특정 값을 넘는 최소 길이 찾기 (O(N))

🔹 문제: 연속된 부분 배열의 합이 S 이상이 되는 가장 짧은 길이를 구하라.

✔ Two Pointer 활용 (O(N))

def min_subarray_length(arr, S):
    left = 0
    min_length = float('inf')
    curr_sum = 0
    
    for right in range(len(arr)):
        curr_sum += arr[right]
        
        while curr_sum >= S:
            min_length = min(min_length, right - left + 1)
            curr_sum -= arr[left]
            left += 1
    
    return min_length if min_length != float('inf') else 0

arr = [2, 3, 1, 2, 4, 3]
S = 7
print(min_subarray_length(arr, S))  # 2 (4+3)

✔ 왼쪽과 오른쪽 포인터를 활용하여 부분 배열의 합을 관리하면서 최소 길이를 찾음.

---

4️⃣ Two Pointer 정리

유형	설명	시간 복잡도
배열 내 두 수의 합	정렬된 배열에서 합이 target인 두 수 찾기	O(N)
부분 배열 문제	특정 조건을 만족하는 최소 길이 찾기	O(N)

📌 Two Pointer 기법을 활용하면 불필요한 탐색을 줄여 시간 복잡도를 개선할 수 있다.