투 포인터(Two Pointers)

투 포인터 개념

---

1차원 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 조작해가면서 원하는 값을 찾을 때까지 탐색하는 알고리즘.

리스트에 순차적으로 접근해야 할 때 두개의 포인터의 위치를 기록하면서 처리한다.

 

동작 방식

1. 시작점과 끝점이 리스트의 양 끝을 가리키도록 한다.

2. 두 포인터가 가르키는 원소의 합이 target sum과 같다면 종료(원하는 값을 찾음)

3. 두 포인터가 가르키는 원소의 합이 target sum보다 작으면 시작점을 1 증가시킨다.

4. 두 포인터가 가르키는 원소의 합이 target sum보다 크면 끝점을 1 감소시킨다.

5. 모든 경우를 확인할 때까지 2~4 과정을 반복한다.

 

문제에 따라 구현되는 방식이 조금씩 다를 수 있음.

두 포인터가 인덱스(0)을 가리키는것에서 시작하는 문제도 있다