Two Pointers

투포인터는 한가지의 포인터로 배열안의 모든 요소를 비교 하는게 비효율적이거나 배열 안에서 페어단위로 조사를 할 필요성이 있을 때 대표적으로 사용되는 알고리즘이다. 

 

투포인터 알고리즘이 사용 되기 좋은 상황의 경우 아래와 같다.

1. 두 배열의 Intersection을 찾을 때

2. 두 배열의 용소를 합칠 때

3. 두 배열의 차이를 찾을 때

즉, 두개의 배열을 사용하는 경우 유용하다.

 

이런 투포인터의 핵심은 포인터와 포인터가 움직이는 조건에 대한 파악이다.

그리고 두개의 포인터이니 조건을 판단하고 어떤 포인터를 움직여야 하는지에 대해 파악이 필요하다.

 

예를들어 주어진 값과 배열 안에서 주어진 값을 만들 수 있는 하나의 페어를 찾아야 하는경우 배열 가장 앞과 뒤에 두개의 포인터를 두고 합이 값보다 클경우 가장 뒤에있는 앞으로 작을 경우 가장 앞의 포인터를 한칸 뒤로 옮겨가면 된다.

 

이렇게 투포인터의 핵심은 시간복잡도를 줄이면서 빠른 구현에 초점을 맞춘다.

 

그래서 Two Pointer의 시간복잡도는 O(nlogn)이고 위의 예시에서  Two Pointers를 사용하지 않는다면 N^2의 시간 복잡도가 필요하다.