1차원 배열이 있고, 배열 안에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 설정한다.
2개의 포인터를 조작해가면서 원하는 것을 얻는 형태의 알고리즘.
투 포인터는 2개의 포인터로 알고리즘의 시간 복잡도를 최적화한다.
배열에서 연속된 데이터 구간에서 처리하기를 원하거나, 정렬된 두 배열이 문제 조건에 있다면, 투포인터 알고리즘을 의심해봐야 한다.
(문제 세부적인 유형에따라 원칙이 다를 수 있다.)
시간복잡도
O(N)
1. 특정 연속된 구간의 합 (구간 넓이 유동적)
이동원칙 (어떤 수의 합 = sum | 기준 : N)
- sum > N : sum = sum - start_index; start_index++;
-> start_index를 오른쪽으로 한 칸 이동하는 것은 연속된 자연수에서 왼쪽 값을 삭제하는 것과 효과가 같다. - sum < N : end_index++; sum = sum + end_index;
-> end_index를 오른쪽으로 한 칸 이동하는 것은 연속된 자연수의 범위를 한 칸 더 확장하는 의미이다. - sum == N : end_index++; sum = sum + end_index; count++;
알고리즘
- 시작점(start)과 끝점(end)이 첫 번째 원소의 인덱스(0)를 가리키도록 한다.
- 현재 부분 합이 M과 같다면, 카운트한다.
- 현재 부분 합이 M보다 작거나 같다면, end를 1 증가시킨다.
- 현재 부분 합이 M 보다 크다면, start를 1 증가시킨다.
- 모든 경우를 확인할 때(end가 끝까지 갈 때까지)까지 2~4 과정 반복
2. 두 수의 합
배열을 먼저 정렬한 후, 투 포인터 i,j를 양쪽 끝에 위치시킨 후 문제의 조건에 적합한 포인터 이동원칙을 활용해 탐색을 수행한다.
이동원칙
- A[i] + A[j] > M : j--;
- A[i] + A[j] < M : i++;
- A[i] + A[j] == M : i++; j-; answer++; //양쪽 포인터 모두 이동!
3. 슬라이딩 윈도우 (구간 넓이 고정)
2개의 포인터로 범위를 지정한 후, 범위를 유지한 채로 이동하며 문제를 해결
