투 포인터(Two Pointers) (Python)

투 포인터 알고리즘이란?

투 포인터 알고리즘이란 일차원 배열에서 말 그대로 2개의 포인터를 이동시키며 원하는 값을 찾아내는 알고리즘을 의미한다.

참고로 두 포인터간의 간격이 항상 동일한 경우 슬라이딩 윈도우 알고리즘과 동일해진다.

 

어떻게 구현할까?

1. 두 포인터의 위치를 저장할 변수를 만든다. (주로 left, right와 같은 단어를 사용한다.)
2. 두 포인터의 초기 위치와 탐색 조건을 지정한다.
   초기 위치는 left = right = 0으로 지정하거나 left = 0, right = n - 1로 지정하는 경우가 많다.
   탐색 조건은 left <= right, right < n 등이 자주 사용된다.
3. 탐색 조건을 만족하지 않을 때까지 left나 right 포인터를 옮긴다.
   각 포인터는 계속 한 방향으로 움직여야 $O(N)$의 시간 복잡도가 보장됨에 주의한다.

 

구현해보기 (Python)

[3273] 두 수의 합 문제를 투 포인터를 이용해 풀어보자.

 

먼저 배열을 정렬한 후, 두 포인터가 가리키는 수들의 합이 $x$이면 개수를 추가해주면 된다.

left는 왼쪽부터, right는 오른쪽부터 탐색할 것인데, left가 오른쪽으로 가면 합은 커질 것이고, right가 왼쪽으로 가면 합은 작아질 것이다.

이를 이용해 포인터를 계속 움직여주면 된다.

 

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))
x = int(input())

# 1. 리스트 정렬
arr.sort()

# 2. 투 포인터 적용
left, right = 0, n - 1
answer = 0

while left < right:
    result = arr[left] + arr[right]
    
    if result <= x:
        left += 1
        if result == x:
            answer += 1
    else:
        right -= 1

print(answer)

 

관련 문제 (BOJ)

• [3273] 두 수의 합
• [1806] 부분합: 누적합 + 투 포인터
• [31411] 대회 개최: 문제에서 그리디적인 요소를 찾은 후 투 포인터로 해결하는 문제