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

SEUNGJUN·2024년 5월 3일

Data Structure & Algorithm

목록 보기

20/20

주로 배열이나 리스트와 같은 순차 데이터 구조에서 사용되는 알고리즘 기법 중 하나이다. 이 알고리즘은 두 개의 포인터를 사용하여 특정 조건을 만족 하는 부분 구간을 찾거나, 두 포인터 사이의 특정 조건을 만족시키는 요소를 찾는 데 사용된다.

투 포인터 특징

1. 두 개의 포인터

투 포인터 알고리즘은 보통 두 개의 포인터를 사용한다. 이러한 포인터는 일반적으로 배열이나 리스트의 시작과 끝을 가리키거나, 서로 다른 부분을 가리킨다.

2. 동시 이동

포인터는 일반적으로 동시에 이동하며, 이동 거리나 방향은 문제의 요구에 따라 다르다.

3. 시간 복잡도

투 포인터 알고리즘의 시간 복잡도는 일반적으로 O(n)이다. 이는 두 포인터가 배열이나 리스트를 한 번만 훑으면서 문제를 해결할 수 있기 때문이다.

적용 문제

부분 배열 또는 부분 리스트 찾기

배열 또는 리스트에서 특정 조건을 만족하는 연속적인 부분 배열 또는 부분 리스트를 찾을 때 사용된다.

두 요소의 합 찾기

배열이 주어졌을 때, 합이 특정 값이 되는 두 요소를 찾는 문제에 투 포인터 알고리즘이 유용하게 사용된다.

정렬된 배열의 특정 합 찾기

정렬된 배열에서 특정 합이 되는 요소 쌍을 찾는 문제에도 투 포인터 알고리즘이 사용된다.

문제

주어진 정렬된 배열에서 특정 합이 되는 두 요소의 인덱스를 찾는 문제이다.

예를 들어, 다음과 같은 배열이 주어졌을 때, 합이 40이 되는 두 요소의 인덱스를 찾는 문제이다.

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
    
    return None

nums = [1, 5, 8, 10, 13, 16, 27, 32, 45, 60]
target = 40

result = two_sum(nums, target)
if result:
    print("두 요소의 합이 {}가 되는 인덱스는 {}입니다.".format(target, result))
else:
    print("해당하는 요소의 조합을 찾을 수 없습니다.")