[파이썬] 순차 접근을 빠르게 : 투 포인터 활용하기

모든 사진과 내용은 강의를 참고 했습니다.

---

투포인터

2 가지 점(시작, 끝점)의 위치를 기록해서, 순차 접근을 빠르게 할 수 있도록 도와주는 알고리즘이다.

투포인터를 사용하면 기존 $O(N^2)$에서 $O(N)$로 시간 복잡도를 줄일 수 있다는 장점이 있다.

• 매 시행 마다 투 포인터의 시작, 끝 점은 1개 씩 움직이고, 각 점이 마지막 성분에 도달하면 끝나게 되기 때문에 $O(N)$ 임

활용 1 : 부분 합 구하기

투포인터는 수열의 부분 합을 구하는데 활용될 수 있고, 수열의 모든 수가 양수인 경우에만 가능하다.

모든 수가 양수여야 시작점을 오른쪽으로 옮길 때, 합을 구성하는 성분 수가 줄어 합이 줄어 들고,

끝점을 오른쪽으로 옮겨 부분 합을 구성하는 성분 수가 늘어 합이 늘기 때문이다.

  

투포인터를 활용해서 부분 합을 구하는 과정을 요약하면 아래와 같다.

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

이를 활용하여 부분합이 5인 부분 연속 수열의 개수를 파악하는 과정을 그림으로 확인해보자.

 

우선 우리가 확인하고 싶은 수열은 아래와 같다.

이제 시작점(s)과 끝점(e)이 첫 번째 원소의 인덱스를 가리키도록 설정하자. 이때의 부분 합은 1이기 때문에 합을 늘리려면결국 끝 점을 옮겨야 한다.

부분 합이 5보다 작아서 끝점을 계속 옮기다 보면, 부분 합이 5보다 큰 경우가 생긴다.

이젠 합을 줄이기 위해서 시작 점을 옮겨야 한다.

이젠 시작점을 옮겨야할 차례

부분 합을 줄이기 위해 시작점을 옮겨보니 합이 5가 됐다. 부분 연속 수열의 개수를 늘릴 수 있게 됐으니, 이제 새로운 부분 연속 수열을 찾기 위해서 시작 점을 옮기고, 끝 점을 옮기는 과정을 반복하자.

과정을 계속 반복하면 남은 부분 연속 수열을 찾을 수 있고, 시작 점이 마지막 성분을 가리키는 순간 탐색은 종료된다.  

시작 점이 마지막 성분에 위치하면 종료!