내일배움캠프 79일차 - 자료구조 & 알고리즘 15주차 : 투 포인터(Two Pointer)

투 포인터

숫자 배열이 정렬되어있을 때, 왼쪽과 오른쪽에서 하나 씩 골라서 조건을 충족할 때까지 가운데에서 만날 때 까지 순회하는 비교 방식.

예를 들어, 두 칸의 합이 100이 되는 경우를 고를 때 순회로 완전 탐색 O(n^2)을 하는 방법도 있지만, 양쪽 끝부터 비교해서, 다음과 같이 조건에 따라 인덱스를 고르면서 중앙에 맞닿을 때 까지 순회하는 방법도 있다.

두 칸의 합에 대해
 - 100보다 작으면 → R번 칸을 한 칸 우측이동
 - 100보다 크면 → L번 칸을 한 칸 좌측이동
 - 100이면 → 정답

위와 같은 비교방식은 100만 칸 배열에 대해 완전 탐색과 비교하면 다음과 같은 연산횟수를 가진다.

완전 탐색(모든 쌍 시도): 5,000억 번
투 포인터(양쪽 끝에서 좁혀오기): 100만 번
 = 50만배의 차이