[알고리즘] 투 포인터(Two pointer)

투 포인터(Two Pointer) 알고리즘이란,
1차원 배열에서 연속된 부분배열을 두 개의 포인터로 조작해 원하는 결과 값을 도출하는 알고리즘이다.

예시

예를 들어보면 부분배열의 합이 5보다 크고 8보다 작은 모든 부분 배열을 구하라 라는 문제가 있을 때, 빨간색 화살표가 부분배열의 시작 인덱스이고 파란색 화살표가 부분배열의 끝 인덱스라고 가정해보자.

1. 시작은 배열의 첫 번째 인덱스에서 두 개의 포인터가 시작한다.
현재 부분배열은 0번째에서 0번째까지 이므로 부분배열의 합은 1이다.
조건에 맞지 않으니 끝 인덱스를 증가시킨다.

2. 위 그림에서 부분배열의 합은 3이된다. 이또한 조건에 맞지 않으니 끝 인덱스를 증가시킨다.

3. 부분배열의 합이 6으로 조건에 만족하는 부분배열이 구해졌다.
해당 인덱스를 저장시키고 시작 인덱스를 증가시켜서 다음 조건에 맞는 부분배열을 찾는다.

4. 해당 동작을 반복해서 두 포인터가 배열의 끝까지 갈 때까지 반복한다.

시간복잡도

해당 알고리즘은 일차원 배열안에 두 개의 포인터가 배열 끝까지 이동하면서 탐색하는 방식이기 때문에 O(2n)의 시간복잡도를 가집니다.
따라서 투 포인터(Two Pointer)의 시간복잡도는 O(n)이라고 할 수 있습니다.

주의할 점

배열의 요소가 자연수가 아니라면 해당 알고리즘은 사용할 수 없습니다.
이유는 부분배열의 시작인덱스가 증가하면 값이 감소되어야하고 끝인덱스가 증가하면 값이 증가되어야하는데 음수가 들어간다면 이를 보장할 수 없기때문 입니다.

---

문제풀이

• 투 포인터 알고리즘