Two Pointer

일반적으로 어떤 수열 $A = {1,2,3,4,5,6…}$ 에서 각각 다른 원소를 가르키고 있는 두개의 포인터를 움직이며

투포인터 없이는 $O(N^2)$ 만에 수행 할 수 있는 연산을 $O(N)$ 만에 해결하는 것을 의미함

특징

두개의 포인터 i, j 가 있다고 할 때, 기존에는 i의 위치 기준에서의 각각의 j를 모두 살펴보는 O(N^2) 의 해결방법이 아니라, i의 위치 기준에서의 각각의 j를 이전의 j까지도 활용할 수 있는 j의 최대 N번의 움직임으로 인해 총 i의 최대 움직임 N, j의 최대 움직임 N = $O(2N)$ 으로 모든 지점을 탐색하여 살펴볼 수 있다.

포인터가 움직여야 할 조건

문제가 가지고 있는 성질(단조증가성, 등등)등을 잘 살펴서 포인터를 적절히 움직여주어야 한다.

예) BOJ 2230 수고르기 문제의 성질:

두 원소의 차가 M이상이면서 가장 작은 값을 구하기 정렬로 인한 단조증가성을 보장시키고, 두 포인터가 바라보고 있는 두 원소에 대해 더 큰 차이 값을 바라보기 위한 해결법

A[j] - A[i] < M 이 참 일 경우 j를 증가 (i를 늘려봐야, 차가 더 작아진다 기대하는 값은 차가 M이상인 값을 찾고자 한다. 그렇다면 당연히 j를 늘려서 차를 더 늘려봐야 한다)

A[j] - A[i] ≥ M이 참 일 경우 i를 증가 (이미 차가 M 이상인 경우이다. 이 경우는 두 포인터가 가지는 두 원소에 대한 차를 찾은 최초지점이라고 볼 수 있다. 이 때 i를 늘려서 최초지점인 j에 대한 나머지 i들을 살펴서 더 작은 차의 값이 나올 가능성이 존재하기 때문에 i를 늘려본다)