[Algorithm] 투 포인터(Two Pointer) 알고리즘 이해하기

Two Pointer Algorithm

투 포인터 알고리즘은 배열이나 리스트와 같은 데이터 구조에서 두 개의 포인터를 사용하여 문제를 효율적으로 해결하는 알고리즘입니다. 이 알고리즘은 주로 정렬된 데이터 구조에서 특정 조건을 만족하는 요소를 찾거나, 부분 배열의 합이나 특정 패턴을 찾는 데 사용됩니다. 투 포인터 알고리즘은 시간 복잡도를 줄이는 데 특히 유용하며, 일반적으로 O(n) 시간 복잡도를 가집니다.

알고리즘의 작동 원리

1. 초기화: 두 개의 포인터를 배열의 시작과 끝에 배치합니다. 이를 통해 배열의 양 끝에서 중앙으로 접근할 수 있습니다. 예를 들어, left 포인터는 배열의 첫 번째 요소를 가리키고, right 포인터는 마지막 요소를 가리킵니다.
2. 조건에 따른 이동:
   • 두 포인터가 가리키는 요소의 합이 목표 값보다 작다면, 더 큰 값을 찾기 위해 left 포인터를 오른쪽으로 이동시킵니다.
   • 합이 목표 값보다 크다면, 더 작은 값을 찾기 위해 right 포인터를 왼쪽으로 이동시킵니다.
3. 반복: 두 포인터가 서로 만나기 전까지 이 과정을 반복합니다. 이를 통해 모든 가능한 쌍을 효율적으로 검사할 수 있습니다.

예시 설명

투 포인터 알고리즘을 이해하기 위해서, 한 방에서 물건을 찾는 상황을 상상해보세요. 방의 양쪽 끝에서 시작해서, 당신과 친구가 서로를 향해 걸어가면서 방을 스캔합니다. 당신이 찾고 있는 특정한 물건이 무엇인지에 따라, 당신들은 각자 한 걸음씩 걸어가면서 확인할 수 있습니다. 만약 당신들이 찾고 있는 물건의 합이 특정 값이라면, 한쪽에서는 더 큰 값을, 다른 쪽에서는 더 작은 값을 찾도록 걸어가게 됩니다.

이 방식은 각자 모든 물건을 일일이 확인하는 대신, 양쪽에서 중앙으로 이동하며 필요한 물건을 빠르게 찾을 수 있게 합니다. 이렇게 하면 불필요한 반복을 줄이고 더 효율적으로 목표를 달성할 수 있습니다.

사용 가능성 판단 기준

투 포인터 알고리즘을 사용하기에 적합한 문제를 판단하기 위해서는 몇 가지 중요한 요소를 고려해야 합니다. 이러한 요소들은 문제의 특성, 데이터 구조의 정렬 여부, 그리고 목표로 하는 조건에 따라 다릅니다.

1. 정렬된 배열 또는 리스트:
   • 정렬된 배열이 주어진 경우, 두 포인터를 양 끝에 배치하여 특정 조건을 만족하는 쌍을 효율적으로 찾을 수 있습니다.
2. 특정 조건을 만족하는 쌍 또는 부분 배열 찾기:
   • 배열에서 특정 조건을 만족하는 쌍이나 부분 배열을 찾는 경우에 유용합니다.
3. 연속된 부분 문자열 또는 서브 시퀀스 문제:
   • 문자열의 회문 검사나 특정 패턴을 찾는 문제에 사용될 수 있습니다.
4. 중복 요소 제거 또는 구간 내 요소 비교:
   • 배열에서 중복 요소를 제거하거나 특정 구간 내 요소를 비교할 때 두 포인터를 사용할 수 있습니다.

예제 문제

1. 두 수의 합 (Two Sum)

정렬된 배열에서 두 수의 합이 특정 값이 되는 쌍을 찾는 문제입니다.

def two_sum(nums, target):
    # 배열의 처음과 끝에서 시작하는 두 포인터를 초기화합니다.
    left, right = 0, len(nums) - 1
    
    # 두 포인터가 만나기 전까지 반복합니다.
    while left < right:
        # 현재 두 포인터가 가리키는 요소의 합을 계산합니다.
        current_sum = nums[left] + nums[right]
        
        # 합이 목표 값과 같은 경우, 인덱스를 반환합니다.
        if current_sum == target:
            return left, right
        
        # 합이 목표 값보다 작은 경우, 더 큰 값을 찾기 위해 왼쪽 포인터를 오른쪽으로 이동합니다.
        elif current_sum < target:
            left += 1
        
        # 합이 목표 값보다 큰 경우, 더 작은 값을 찾기 위해 오른쪽 포인터를 왼쪽으로 이동합니다.
        else:
            right -= 1
    
    # 목표 값을 만족하는 쌍을 찾지 못한 경우, (-1, -1)을 반환합니다.
    return -1, -1

이 코드에서 two_sum 함수는 두 포인터를 사용하여 배열에서 목표 합이 되는 두 숫자의 인덱스를 찾습니다.

2. 최소 길이 부분 배열 (Minimum Length Subarray)

부분 배열의 합이 특정 값 이상이 되는 최소 길이의 부분 배열을 찾는 문제입니다.

def min_sub_array_len(target, nums):
    # 왼쪽 포인터를 배열의 시작 위치에 초기화합니다.
    left = 0
    
    # 현재 부분 배열의 합을 저장할 변수와 최소 길이를 무한대로 초기화합니다.
    current_sum = 0
    min_length = float('inf')
    
    # 오른쪽 포인터를 배열의 모든 요소에 대해 이동시킵니다.
    for right in range(len(nums)):
        # 현재 요소를 부분 배열의 합에 추가합니다.
        current_sum += nums[right]
        
        # 현재 합이 목표 값 이상인 동안 반복합니다.
        while current_sum >= target:
            # 부분 배열의 길이를 계산하고, 최소 길이를 업데이트합니다.
            min_length = min(min_length, right - left + 1)
            
            # 왼쪽 포인터가 가리키는 요소를 부분 배열의 합에서 빼고, 왼쪽 포인터를 오른쪽으로 이동합니다.
            current_sum -= nums[left]
            left += 1
    
    # 최소 길이가 업데이트된 경우 그 값을, 그렇지 않은 경우 0을 반환합니다.
    return min_length if min_length != float('inf') else 0

이 코드는 두 포인터를 사용하여 부분 배열의 합이 주어진 값 이상이 되는 최소 길이의 부분 배열을 찾습니다. right 포인터를 이동시켜 부분 배열을 확장하고, left 포인터를 이동시켜 부분 배열을 축소하며 조건을 만족하는 최소 길이를 계산합니다.

시간 및 공간 복잡도

• 시간 복잡도: 일반적으로 O(n)입니다. 각 포인터는 배열이나 리스트를 한 번씩만 순회하기 때문에 선형 시간 내에 문제를 해결할 수 있습니다.
• 공간 복잡도: O(1)입니다. 추가적인 데이터 구조를 사용하지 않고, 기존 배열이나 리스트 내에서 포인터만을 사용하여 문제를 해결합니다.

결론

투 포인터 알고리즘은 배열이나 리스트에서 효율적으로 특정 조건을 만족하는 요소를 찾는 데 매우 유용합니다. 정렬된 데이터에서 특히 효과적이며, 시간 복잡도를 O(n)으로 줄일 수 있습니다. 이 알고리즘은 다양한 문제에 적용할 수 있어 알고리즘 문제 해결 능력을 향상시키는 데 큰 도움이 됩니다.

투 포인터 알고리즘을 이해하고 적용하는 것은 효율적인 문제 해결을 위한 중요한 도구입니다. 이 알고리즘을 잘 활용하면, 문제를 빠르고 효과적으로 해결할 수 있으며, 복잡한 문제도 보다 단순하게 접근할 수 있습니다.