투 포인터 (Two Pointers)
- 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하며 나아가는 알고리즘이다
- 시작점과 끝점을 그 두개의 점으로 지정한다
- 특정한 합을 가지는 부분 연속 수열 문제에 적용 가능하다
- 두 개의 점이므로 투 포인터라 한다
- 반복문만 사용하는 것보다 메모리와 시간 효율성을 높일 수 있다
- 시간 복잡도는 O(N) 이다 (반복문 사용시 O(N^2))
앞에서 시작하는 포인터 & 끝에서 시작하는 포인터
- 두 포인터 중 start 포인터를 가장 앞 인덱스 0으로 설정하고, 나머지 end 포인터를 가장 마지막 인덱스 n으로 설정한다.
- 찾아야 하는 값 < 두 점의 합 → end 포인터를 인덱스를 하나 줄여 감소
- 찾아야 하는 값 > 두 점의 합 → start 포인터를 인덱스 하나 늘려 증가
- start와 end 포인터가 동일한 값을 가리키면 종료 (중간에서 만나는 경우)
- 조건 : 배열이 정렬되어 있어야 하며 중복되는 수가 없어야 한다
- 주로 2중 for문을 사용하여 코드를 작성
토끼와 거북이
- 제일 앞부터 시작하지만 두 포인터가 속도가 다르게 움직인다.
- 주로 slow와 fast 포인터로 이름을 붙인다.
- 주로 fast는 반복문마다 값이 커지고 slow는 조건에 따라 값이 커지도록 설정한다.
- 두 포인터 slow와 fast를 각각 인덱스 0과 1로 지정한다.
- 주로 정렬된 배열에서 중복되는 숫자를 제거할 때 사용한다.
- 이때 새로운 리스트를 생성하는 것이 아닌 리스트의 요소들을 변경하는 형식으로 진행되는 것이다.