투포인터(Two Pointer) 알고리즘

투포인터 알고리즘의 정의

투포인터 알고리즘(Two Pointers Algorithm) 혹은 슬라이딩 윈도우(Sliding Window)라 부른다.

알고리즘 문제 중 완전 탐색으로 풀면 시간초과가 나는 문제일 때, 투포인터 알고리즘을 떠올려 보아야 한다.

투포인터 알고리즘에는 1차원 배열이 있고, 이 배열에서 서로 다른 두 개의 포인터를 이용해 원소에 접근하며 원하는 것을 얻는다.

 

• 원래 이중 for문으로 $O(N^2)$에 처리되는 작업을 2개의 포인터를 이용하여 $O(N)$에 해결하는 알고리즘이다.

예시

크기가 N인 1차원 배열 arr가 있다. 이 때 arr의 부분 배열 중 그 원소의 합이 M이 되는 경우의 수가 몇 개 인지를 구해보자.
이를 완전 탐색으로 모든 경우의 수를 전부 테스트하는 것은,  $O(N^2)$의 시간복잡도를 가진다.

이를 투포인터 알고리즘으로 풀기 위해서
1. 포인터 s(start)와 포인터 e(end)를 둔다.
2. 초기 설정은 s = e = 0이며, 두 포인터는 s <= end를 항상 만족한다.

포인터 s와 e로 다음 과정을 s<N 를 만족하는 동안 반복한다.
1. 만약 현재 부분합이 M 이상이거나 e = N이면 s++
2. 그렇지 않다면 e++
3. 현재 부분합이 M이라면 결과값++1

위처럼 start과 end를 한 방향으로 계속 증가시켜가면서 부분 배열의 합이 M이 되는 경우를 찾아내는 것이다.
각 포인터가 N을 가르키면 종료되므로, 이 알고리즘의 시간복잡도는 O(N)이다.

문제 특징

• 이분 탐색으로 풀 수 있는 문제는 투 포인터로 풀 수 있는 경우가 많다.
• 반대로 투 포인터 문제를 이분 탐색으로 풀 수 있는 경우도 많다.
• end의 인덱스 예외처리를 주의해야 한다.

---

문제집

https://www.acmicpc.net/workbook/view/8709

• 복습하기 좋은 문제
  https://www.acmicpc.net/problem/10816

---

참고 : https://m.blog.naver.com/kks227/220795165570