투 포인터(Two Pointers)

게시 2024/02/25

By 신건우 7 분읽는 시간

배열에 순차적으로 접근해야 할 때, 두 개의 포인터(지점)를 이용하는 알고리즘

배열 [1,2,3,4,5,6,7,8] 에서 2,3,4,5,6,7번 원소를 골라야할 때, 간단하게 ‘2번부터 7번까지의 원소’라고 부를 수 있다.

즉, 투 포인터 알고리즘은 두 개의 포인터가 하나의 ‘범위’를 나타내는 것을 활용한다.

1차원 배열 : 부분 배열
2차원 배열 : 사각형 모양의 구간

배열 내에서 연속된 값들을 이용해서 문제를 해결해야할 때, **두 개의 인덱스를 나타내는 변수들을 움직**이며 효율적으로 탐색하여 문제를 해결하는 알고리즘이다.

예시

특정한 합을 가지는 부분 연속 수열 찾기

시작점(start)과 끝점(end)이 첫번째 원소의 인덱스(0)를 가리키도록 한다.
현재 부분 합(부분 배열의 합)이 M과 같다면, 카운트한다.
현재 부분 합이 M보다 작다면, end를 1 증가시킨다. (부분 합이 증가)
현재 부분 합이 M보다 크거나 같다면, start를 1 증가시킨다. (부분 합이 감소)
모든 경우를 확인할 때까지 2번부터 4번까지의 과정을 반복한다.

  
def two_pointer_algorithm(array, M):
    start, end = 0, 0
    current_sum = array[0]
    count = 0
  
    while end < len(array) and start <= end:
        if current_sum == M:
            count += 1
            end += 1
            if end < len(array):
                current_sum += array[end]
        elif current_sum < M:
            end += 1
            if end < len(array):
                current_sum += array[end]
        else:  # current_sum > M
            current_sum -= array[start]
            start += 1
            if start > end and start < len(array):
                end = start
                current_sum = array[start]
    return count
  
# 예제 사용
array = [1, 2, 3, 4, 2, 5, 3, 1, 1, 2]  # 임의의 배열
M = 5  # 목표 합
print(two_pointer_algorithm(array, M))  # 결과 3이 출력

브루트포스 방식을 사용하면 $O(N^2)$ 이 걸리나, 투 포인터를 이용하면 $O(N)$에 해결가능하다.

투 포인터와 이분탐색

투 포인터 문제가 이분탐색으로도 풀리거나, 이분탐색 문제가 투 포인터로 풀리는 경우가 자주 존재한다.

시간복잡도 면에서 투 포인터는 $O(N)$인 반면, 이분탐색은 $O(N\log N)$이다.

$\log N$의 차이로 시간복잡도를 통과하지 못하는 경우는 거의 없다.

다만 투 포인터로만 풀어야 하는 문제가 존재한다. 해당 문제의 특성에 대해서 살펴보자.

연속된 부분 배열에 대한 문제
투 포인터 알고리즘은 배열에서 연속된 부분 배열에 대한 문제를 풀 때 매우 효율적이다. 이분탐색의 경우에는 배열 내의 원소들이 정렬되어 있거나 정렬 가능한 상태여야 하지만, 투 포인터 알고리즘은 연속성이 중요한 문제에서 더 유용하다.
배열이 정렬되어 있거나, 정렬의 필요성이 없는 문제
투 포인터 알고리즘은 배열의 원소들이 정렬되어 있을 때, 특히 오름차순이나 내림차순 정렬이 되어있을 때 효과적이다. 이분탐색은 배열이 정렬되어 있을 때만 사용할 수 있지만, 투 포인터 알고리즘은 정렬의 필요성이 없는 문제에도 적용할 수 있다.
- 정렬된 배열에서의 투 포인터
  이 경우, 하나의 포인터는 배열의 시작점에서, 다른 하나는 배열의 끝점에서 시작한다. 두 합이 목표값보다 작으면 시작점의 포인터를 오른쪽으로, 크면 끝점의 포인터를 왼쪽으로 이동한다.
  이 방법은 주로 두 수의 합이나 차를 찾는 문제에 사용된다.
- 정렬되지 않은 배열에서의 투 포인터 (정렬을 시킬 수 없는 경우)
  이 경우, 두 포인터는 배열의 시작점에서 출발한다. 현재 부분 배열의 합이 목표값보다 작으면 끝점의 포인터를 오른쪽으로, 크거나 같으면 시작점의 포인터를 오른쪽으로 이동시킨다.
  이 방법은 주로 연속된 부분 배열의 합을 찾는 문제에 사용된다.
배열 내의 합이나 차에 대한 문제
투 포인터 알고리즘은 배열 내의 두 원소의 합이나 차, 또는 특정 조건을 만족하는 부분 배열의 합 등을 구하는 문제에서 효과적이다.
시간 복잡도에 대한 제한이 있는 문제
투 포인터 알고리즘은 O(N)의 시간 복잡도를 가지므로, 시간 복잡도에 대한 제한이 있는 문제에서 이분탐색보다 더 효율적일 수 있다.

참고 자료

Algorithm, Structure

Algorithm two pointer

예시

투 포인터와 이분탐색

참고 자료

인기 태그