[알고리즘] 투 포인터 Two Pointers

투 포인터 알고리즘이란?

- 1차원 배열에서 두 개의 포인터(시작점, 끝점)의 위치를 기록하면서 목표값을 구하는 알고리즘. 

- 완전탐색 O(n^2) -> O(n) 선형 시간 복잡도로 문제 해결 가능

- 연속된 구간의 원소들을 처리하거나, 정렬된 배열에서 무언가를 구할 때 사용

 

포인터 두 개가 한 곳에서 시작하는 경우

end 포인터가 0 에서 n 까지 움직일 때 까지 (배열의 길이만큼 순회하며) 반복하므로 

O(n)의 시간복잡도를 가진다. (Linear time 선형 시간 복잡도)

 

1. 시작점과 끝 점이 첫번째 원소의 인덱스를 가리키도록 한다. 

2. 부분합이 S보다 작으면 end ++

3. 부분합이 S보다 크거나 같으면 start ++

4. 문제에서 제시한 부분합의 조건을 만족시킬 경우 처리

모든 경우를 확인할 때까지 2~4번 과정을 반복

 

포인터 두 개가 배열의 각 끝에서 (정 반대의 위치에서) 시작하는 경우

배열이 정렬되어있을 때에만 사용 가능한 패턴? 

정렬이 된 배열에서만 

 

 

예시 문제

- 수들의 합2

https://www.acmicpc.net/problem/2003

- 부분합