투포인터(Two Pointers)

1차원 배열이 있을 때, 이 배열을 가리키는 두 개의 포인터를 조작해 원하는 결과를 얻는 기법

시간 복잡도: O(N) + O(N) = O(N)

설명

1. 초기 포인터 2개를 설정 => start, end (0으로 설정)
2. start ~ end 범위는 현재 탐색할 리스트의 범위
3. start는 항상 end보다 같거나 작다
4. 포인터는 항상 증가하는 방향으로만 움직인다

포인터가 움직이는 조건

1. 현재 부분 배열이 조건보다 작을 때
   • end를 증가
2. 현재 부분 배열이 조건보다 클 때
   • start를 증가
3. 현재 부분 배열이 조건과 같을 때
   • 정답에 추가
   • end를 증가

예시

1. 특정 합을 가지는 부분 연속 수열 찾기
2. 정렬되어 있는 두 리스트의 합집합
3. 리스트 내의 특정 범위 사이에서 특정 조건을 만족하는 값 찾기

• 대표예시: 2020 KAKAO INTERNSHIP 보석쇼핑(67258)

추가

• 투포인터의 start, end의 시작 위치는 [0, 0]이 될 수도 있고 [0, 끝idx]가 될 수도 있다.
• 문제에 따라 시작점의 위치가 바뀔 수 있고, 가장 최적의 시작점을 잡는것이 key point
• 참고 자료: https://github.com/rhs0266/FastCampus/blob/main/%EA%B0%95%EC%9D%98%20%EC%9E%90%EB%A3%8C/02-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98/07~08-%EB%91%90%20%ED%8F%AC%EC%9D%B8%ED%84%B0/02-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-07-%EB%91%90%20%ED%8F%AC%EC%9D%B8%ED%84%B0.pdf