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

투 포인터 알고리즘

• 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 진행하는 알고리즘입니다.
• 완전탐색 알고리즘 등을 사용하여 문제에 접근할 경우 테스트 케이스에 큰 값(엄청 긴 배열이나 범위)이 나오면 시간 초과가 걸리는 경우가 있습니다. 이 때 투 포인터를 사용하면 메모리와 시간 효율성을 높일 수 있습니다.
• 시간복잡도 O(N)으로 O(N^2) 인 이중 for문 보다 효율적이다.

---

사용방법

1. 두 개의 포인터가 배열의 시작점에서 같이 출발하며, 빠른 포인터(fast runner)가 느린 포인터(slow runner)보다 앞서서 진행하는 방식

2. 배열 시작점에서 시작하는 포인터와 끝에서 시작하는 포인터로 진행하는 방식