투 포인터(Two Pointers)

투 포인터(Two Pointers)

화살표 두 개의 의미를 부여해서 탐색 범위를 압축하는 방법!

사용방법과 특징

보통 left(l), right(r) 이나 start(s), end(d) 같은 식으로 포인트의 이름을 붙임
위처럼 포인트 2개를 준비한다. 여기서는 start, end 라고 명칭하겠다. 찾는 값은 target이다.
처음에는 start=end=0 이고, 조건은 항상 두 포인터들의 관계는 start<=end이다.
2개의 포인터는 현재 부분 배열의 시작(start)과 끝(end)을 가르킨다

• 1차원 배열에서 각자 다른 원소를 가리키는 2개의 포인터를 사용하여 목표값을 구한다
• 완전탐색O(n2) 을 -> O(n)으로 성능 향상 가능
• 연속된 구간의 원소들을 처리하기를 원하거나 정렬된 배열에서 무언가를 구할때 투포인터를 사용