[Algorithm] 투 포인터(Two Pointer)

투포인터 알고리즘

• 투포인터는 두 개의 포인터를 기준으로 검색을 하며, 원하는 값을 찾는 알고리즘입니다.
• 두 개의 점을 시작점과 끝점으로 이용하게 되면, 데이터의 범위를 표현 가능하며, 메모리와 시간 효율성을 높일 수 있습니다.

 

사용 예제

1. 특정한 합을 가지는 부분 연속 수열 찾기

• 부분 연속 수열의 시작점(start)과 끝점(end)의 위치를 기록
• 특정한 부분합을 M이라 가정할 때 알고리즘은 아래와 같다.

1. 시작점(start)과 끝점(end)이 첫 번째 원소의 인덱스(0)를 가리키도록 한다.
2. 현재 부분합이 M과 같다면 카운트한다.
3. 현재 부분합이 M보다 작으면 끝점(end)를 1 증가시킨다.
4. 현재 부분합이 M보다 크거나 같으면 시작점(start)을 1 증가시킨다.
5. 모든 경우를 확인할 때까지 2번부터 4번 과정을 반복한다.

 

관련 문제

https://www.acmicpc.net/problem/2003

2003번: 수들의 합 2