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

투포인터

---

1차원 배열이 있고, 이 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터(idx)를 조작해가며 원하는 것을 얻는 형태이다. 부분 배열 중 그 원소의 합이 조건과 일치하는 경우의 수를 구하는 것이다.

모든 경우의 수를 다 테스트한다면 구간의 합을 구간 배열로 O(1)만에 구한다고 해도 경우의 수는 O(N^2)이기 때문에 시간 복잡도를 고려하는 문제라면 풀 수 없다. 배열의 최대 범위가 너무 크기 때문이다.

 

 

예시 / 그림 참조 : https://butter-shower.tistory.com/226

---

X = 5를 구하는 문제에서