[알고리즘 유형 / 접근법] 투 포인터

포인터 ?

C에서 포인터라는 개념이 있다. 어떤 변수의 주소를 값으로 갖는 변수인데,
알고리즘에서 이와 비슷한 개념을 활용하여 문제를 해결할 수 있다.

투 포인터

배열, 리스트 같은 순차 자료구조에서 특정 범위를 탐색하거나, 부분 수열(문자열) 등을 찾는 문제에서 사용할 수 있다.
위와 같은 문제에서, 그냥 단순하게 반복문을 만들어 문제를 풀었는데, 시간 초과가 날 경우, 고려해 볼 수 있다.
투 포인터는 배열이나 리스트에서 인덱스를 저장하는 두 개의 변수를 활용하여 두 위치를 기록하며 문제를 처리하는 알고리즘이다. O(n)

예제

• 특정 합을 가지는 부분 연속 수열 찾기
  https://www.acmicpc.net/problem/2559
• 같은 정수를 K개 포함한 최장 연속 부분 수열 찾기
  https://www.acmicpc.net/problem/20922