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

투 포인터 기법은 배열이나 리스트를 탐색하는 데 매우 효율적인 알고리즘 기법입니다. 두 개의 포인터를 사용하여 문제를 해결하는 이 기법은 주로 정렬된 데이터에서 특정 조건을 만족하는 쌍을 찾는 데 유용합니다. 이 기법은 많은 경우에 O(N) 또는 O(N^2)의 시간 복잡도를 가지며, 최적화된 솔루션을 제공합니다.

 

투 포인터(Two Pointer) 기본 개념

투 포인터 기법은 다음 두 가지 주요 방식으로 사용됩니다:

1. 양 끝에서 시작하기
   • 적용 예: 정렬된 배열에서 두 수의 합이 목표 값과 일치하는 쌍을 찾는 문제
   • 방법: 배열의 시작과 끝에 각각 포인터를 두고, 두 포인터가 가리키는 값의 합을 계산합니다. 합이 목표 값과 같으면 쌍을 찾은 것이고, 그렇지 않으면 포인터를 조정합니다.
2. 같은 방향으로 이동하기
   • 적용 예: 특정 합을 가지는 연속된 부분 배열을 찾는 문제
   • 방법: 하나의 포인터를 배열의 시작 위치에 설정하고, 다른 포인터를 오른쪽으로 이동시키면서 현재 서브 배열의 합을 유지합니다. 합이 목표 값과 같으면 결과를 반환하고, 그렇지 않으면 포인터를 조정합니다.

 

양 끝에서 시작하는 투 포인터 기법

문제: 정렬된 배열에서 두 수의 합이 목표 값과 일치하는 쌍을 찾습니다.

def two_sum(arr, target):
    left = 0
    right = 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, 2, 3, 4, 5, 6]
target = 7
print(two_sum(arr, target))  # 출력: (1, 6)

설명:

• 포인터를 배열의 양 끝에 설정합니다.
• 두 포인터가 가리키는 값의 합을 계산하고, 목표 값과 비교합니다.
• 합이 목표 값과 같으면 쌍을 반환하고, 그렇지 않으면 포인터를 조정하여 계속 탐색합니다.

 

같은 방향으로 이동하는 투 포인터 기법

문제: 배열에서 특정 합을 가지는 연속된 부분 배열을 찾습니다.

def subarray_sum(arr, target):
    current_sum = 0
    left = 0
    
    for right in range(len(arr)):
        current_sum += arr[right]
        
        while current_sum > target and left <= right:
            current_sum -= arr[left]
            left += 1
        
        if current_sum == target:
            return (left, right)
    
    return None

# 예시 사용
arr = [1, 2, 3, 7, 5]
target = 12
print(subarray_sum(arr, target))  # 출력: (1, 3)

설명

• left와 right 포인터를 사용하여 서브 배열의 합을 조정합니다.
• right 포인터를 오른쪽으로 이동시키면서 현재 합을 업데이트합니다.
• 현재 합이 목표 값보다 크면 left 포인터를 이동시켜 합을 줄입니다.
• 현재 합이 목표 값과 같으면 서브 배열의 시작과 끝 인덱스를 반환합니다.

 

장점과 단점

장점:

• 효율성: O(N) 시간 복잡도로 효율적인 탐색이 가능합니다.
• 간단한 구현: 코드가 직관적이고 구현이 비교적 간단합니다.

단점:

• 정렬 필요: 대부분의 문제는 배열이 정렬되어 있어야 합니다.
• 문제 한정: 모든 문제에 적용할 수 없으며, 주로 정렬된 배열이나 특정 조건이 있는 문제에 적합합니다.