투 포인터 알고리즘이란?
투 포인터 알고리즘이란 일차원 배열에서 말 그대로 2개의 포인터를 이동시키며 원하는 값을 찾아내는 알고리즘을 의미한다.
참고로 두 포인터간의 간격이 항상 동일한 경우 슬라이딩 윈도우 알고리즘과 동일해진다.
어떻게 구현할까?
- 두 포인터의 위치를 저장할 변수를 만든다. (주로 left, right와 같은 단어를 사용한다.)
- 두 포인터의 초기 위치와 탐색 조건을 지정한다.
초기 위치는 left = right = 0으로 지정하거나 left = 0, right = n - 1로 지정하는 경우가 많다.
탐색 조건은 left <= right, right < n 등이 자주 사용된다. - 탐색 조건을 만족하지 않을 때까지 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] 대회 개최: 문제에서 그리디적인 요소를 찾은 후 투 포인터로 해결하는 문제
