2 pointer
list에서 각각의 원소를 가르키는 pointer 2개를 사용하여 탐색하는 알고리즘.
- O(n)의 시간복잡도를 가진다.
- 각 포인터가 단일 방향으로 독립적으로 이동한다.
고려사항
2 pointer를 사용해서 문제를 풀려고하는 경우, 3가지에 대한 고려를 하면 문제가 풀린다.
- 포인터 초기화 방법
- 포인터 이동 방법
- 멈춰야 하는 때
활용
두 포인터의 속도와 방향을 달리하여 다양하게 활용할 수도 있다.
- collision - 하나의 배열로 서로를 향해 이동.
- forward - 하나의 배열로 같은 방향으로 이동
- parallel - 2개의 배열로 각각 이동
- sliding window - 2 포인터가 k의 속도차이로 이동
- fast/slow - 포인터 하나는 빠르게 하나는 느리게 이동.
예시
정렬된 배열 nums에서 값의 합이 40이 되는 원소쌍을 찾는다고 했을 때.
백준 3273번 - 두수의 합