투 포인터 (Two Pointers)

투 포인터

투 포인터 알고리즘은, 배열이나 문자열에서 두 개의 포인터(=인덱스)를 사용해서 탐색 범위를 줄이는 알고리즘. 특히, 다중 반복문을 사용해서 모든 쌍을 확인해야 하는 경우에 문제를 더 효율적으로 풀 수 있도록 해준다.
 
만약, 배열에서 모든 쌍을 확인해야 한다면 이중 for문으로 $O(N^2)$의 시간복잡도를 통해 확인할 수 있지만, 조건이 존재한다면 투 포인터를 이용해 포인터를 조건에 따라 움직이며 $O(N)$의 시간복잡도만으로 해결할 수 있다. 즉, 모든 경우를 확인하는 대신에 조건에 맞는 경우를 찾아서 순회하는 알고리즘이라고 할 수 있다.
 
이러한 투 포인터로 풀 수 있는 문제 중 다수는 이분 탐색으로도 풀 수 있고, 이분 탐색으로 풀 수 있는 문제도 마찬가지로 투 포인터로 풀 수 있는 문제가 많다.
 
세 가지 방법으로 투 포인터를 구현할 수 있다:

1. start, end가 모두 첫 번째 원소부터 시작해서 이동하는 경우
2. start 는 배열의 처음, end는 배열의 끝을 나타내어 범위를 좁혀나가는 경우
3. 첫 번째 탐색에서 조건을 만족하는 start 의 위치를 찾고, 해당 위치로부터 end의 위치를 탐색하는 경우

 

즉, 각 start 위치의 값에 대해서 모든 가능한 end 위치를 보는 것이 아니라, 이전 시점의 end 값을 계속 가지고 있다가 조건에 맞게 효율적으로 이를 이용하는 것으로 볼 수 있다.

 

특정 부분 합 이상을 만족하는 최소 길이의 수열 찾기

길이 N짜리 자연수 수열이 주어졌을 때, 연속된 수들의 부분합 중에 그 합이 S 이상인 것 중 가장 짧은 수열의 길이를 구하시오.

위 문제를 보고 제일 먼저 떠올릴 수 있는 알고리즘은 DP에서 다뤘던 Prefix Sum이다. 그러나, 모든 위치에서의 Prefix Sum을 구해도, 수열의 처음 위치와 끝 위치를 탐색하기 위해서는 이중 for문을 이용해 모든 경우의 수에서 부분합의 값을 구해 비교해야 한다. 즉, $O(N^2)$의 시간복잡도로 해결할 수 있다.
 
그러나 투 포인터를 사용한다면 $O(N)$으로 구현할 수 있다.

1. start, end 포인터를 배열의 맨 처음 인덱스로 설정하고, 현재의 부분합 cur_S = arr[start]로 설정한다.
2. cur_S < S인 경우, cur_S에다 end에 위치한 값을 더하고 end를 오른쪽으로 한 칸 옮긴다.
3. cur_S >= S인 경우, 현재 수열의 길이 end - start + 1을 기존 수열의 최소 길이와 비교해서 더 짧은 값을 최솟값으로 둔다. 그리고 cur_S에다 start 에 위치한 값을 빼고 start 를 오른쪽으로 한 칸 옮긴다.
4. 2~3을 반복하다가, end가 배열의 인덱스를 벗어나게 되면 탐색을 종료한다.

 
왜 이러한 알고리즘이 작동할까?

• arr[start] + ... + arr[end] < S 인 경우, end 를 오른쪽으로 이동시키면 새로운 값이 더해지므로 S 에 가까워진다.
• arr[start] + ... + arr[end] >= S 인 경우, start 를 오른쪽으로 이동시켰을 때, 더 작은 길이의 수열이 되므로 항상 옮기지 않았을 때보다 좋은 선택이다.

 
Python으로 구현하면 아래와 같다.

def min_sequence_len(num_list: List[int], S: int) -> int:
    """
    Args:
        num_list: 자연수로 구성된 수열
        S: 만족해야하는 최소 부분합
    Return:
        int: S 이상의 부분합을 갖는 수열 중 최소 길이
    """
    start = 0
    end = 0
    cur_S = num_list[0]
    min_len = float('inf')

    while True:
        if cur_S < S:
            end += 1
            if end >= len(num_list):
                break
            cur_S += num_list[end]
        else:
            min_len = min(min_len, end - start + 1)
            cur_S -= num_list[start]
            start += 1

    return min_len if min_len != float('inf') else 0

 

References

• 바킹독의 실전 알고리즘 0x14: 투 포인터
• https://sehun5515.tistory.com/62
• https://bytebytego.com/courses/coding-patterns/two-pointers/introduction-to-two-pointers?fpr=javarevisited