(Algorithm) Two Pointers Technique [투 포인터]

- 목차

 

소개.

두 개의 배열 또는 리스트가 존재한다고 가정하겠습니다.
그리고 문제의 상황은 두 자료구조가 공통으로 가지는 값들을 추출하는 상황입니다.
이때, 여러가지 알고리즘이 사용될 수 있습니다.
하지만 필연적으로 배열의 각 값들을 비교하는 알고리즘을 반드시 사용해야하는데요.
그 기술들 중에서 시간복잡도가 낮은 방식인 Two Pointers 에 대해서 알아보려고 합니다.

Two Pointers (투 포인터).

투 포인터는 두개의 자료구조를 동시에 순회합니다.
보통 이중 반복문을 활용하여 O(n) 이 n 의 제곱인 방식으로 순회하며 비교하곤합니다.
투 포인터는 이중 반복문을 사용하지 않고 2개의 포인터 변수를 사용합니다.
바로 예시를 통해서 설명을 이어가도록 하겠습니다.

def common_elements(arr1, arr2):
    arr1.sort()
    arr2.sort()
    result = []
    pointer1 = 0
    pointer2 = 0

    while pointer1 < len(arr1) and pointer2 < len(arr2):
        if arr1[pointer1] == arr2[pointer2]:
            result.append(arr1[pointer1])
            pointer1 += 1
            pointer2 += 1
        elif arr1[pointer1] < arr2[pointer2]:
            pointer1 += 1
        else:
            pointer2 += 1

    return result

최우선적으로 비교하고자하는 두 배열은 반드시 정렬이 되어있어야합니다.
정렬의 이유는 모든 값들을 일일이 탐색하지 않고 건너뛰기 위함입니다.
예를 들어,
arr1 : 1, 2, 3, 4, 5
arr2 : 3, 4, 5, 6, 7
인 상황에서 두 배열이 가지는 공통의 값들은 3,4,5입니다.
arr1 과 arr2 는 정렬되어 있기 때문에 arr1 이 가지는 1, 2 값은 비교 대상에서 쉽게 제외될 수 있습니다.
보통 정렬 알고리즘은 퀵소트나 머지소트를 사용하며,
이들의 시간복잡도는 O(n)=nlog(n) 으로 시간복잡도가 크지 않습니다.

그리고 정렬이 마무리되었다면, 두 개의 포인터 변수를 활용하여 비교 탐색을 시작합니다.
두 배열이 가지는 첫번째 위치의 값들을 먼저 비교합니다.
작은 값을 가지는 배열의 포인터는 1씩 증가합니다.
이러한 과정을 반복하다보면,
서로 동일한 값을 가지는 순간이 찾아옵니다.
그럼 해당하는 값을 저장한 후, 서로의 포인터는 증가시킵니다.
그리고 투 포인터 비교를 반복합니다.

시간복잡도.

투 포인터 알고리즘의 시간복잡도는 어떻게 될까요 ?
이는 O(n) = n + m 입니다.
n 과 m 은 각각 배열의 길이입니다.
시간복잡도는 두 배열의 길이의 합에 비례하게됩니다.

Two Pointers 가 필요한 사례들.

 

1. 배열의 두 값의 합이 a 인 조합들 찾기.

어떠한 배열이 있고, 이 배열의 두 값을 더한 값이 a 가 되는 조합을 찾은 케이스가 있을 수 있습니다.
예를 들어, arr : 1,2,3,4,5,6,7 이 있을때
두 값의 합이 8이 되는 조합은 (1,7), (2,6), (3,5) 가 있습니다.
이때에서 투 포인터가 사용될 수 있습니다.
코드 예시는 아래와 같습니다.

def find_pair(nums, target):
    left, right = 0, len(nums) - 1

    while left < right:
        current_sum = nums[left] + nums[right]

        if current_sum == target:
            return [nums[left], nums[right]]
        elif current_sum < target:
            left += 1
        else:
            right -= 1

    return None

# Example usage
sorted_array = [-2, 1, 2, 4, 7, 11]
target_sum = 9
result = find_pair(sorted_array, target_sum)
print(result)  # Output: [2, 7]

투포인터 변수는 배열의 시작과 끝에 두고,
투포인터 사이의 간격을 좁혀가며, 탐색과 비교를 진행합니다.