투포인터(Two Pointers)

투 포인터(Two Pointers)알고리즘은 리스트에 순차적으로 접근해야 할 때 2개의 점의 위치를 기록하면서 처리하는 알고리즘을 의미한다.

리스트에 담긴 데이터에 순차적으로 접근해야 할 때는 ‘시작점'과 ‘끝점' 2개의 점으로 접근할 데이터의 범위로 표현해야할때 사용한다.

예시) ‘특정한 합을 가지는 부분 연속 수열 찾기'

양의 정수로만 구성된 리스트가 주어졌을 때, 그 부분 연속 수열 중에서 ‘특정한 합'을 갖는 수열의 개수를 출력하는 문제이다.

 

 

이때 합계 값을 5라고 설정하면 다음과 같은 3가지 경우의 수만 존재한다.

 

 

투 포인터 알고리즘의 특징은 2개의 변수를 이용해 리스트 상의 위치를 기록한다는 점이다. 부분 연속 수열의 시작점(start)과 끝점(end)의 위치를 기록한다. 특정한 부분합을 M이라고 할 때, 구체적인 알고리즘은 다음과 같다.

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

step 0

알고리즘에 따라서 초기 단계에서는 시작점과 끝점이 첫 번째 원소의 인덱스를 가리키도록 한다. 이때 현재의 부분합은 1이므로 무시한다.

 

step 1

이전 단계에서의 부분합이 1이었기 때문에 end를 1 증가시킨다. 현재 부분합은 3이므로 이번에도 마찬가지로 무시한다.

 

step 2

이전 단계에서의 부분합이 3이었기 때문에 end를 1 증가시킨다. 현재 부분합은 6이므로 이번에도 마찬가지로 무시한다.

 

step 3

이전 단계에서의 부분합이 6이었기 때문에 start를 1 증가시킨다. 현재 부분합이 5이므로 하나의 경우를 찾은 것이다. 따라서 카운트 한다.

 

step 4

이전 단계에서의 부분합이 5였기 때문에 start를 1 증가시킨다. 현재 부분합은 3이므로 무시한다.

 

step 5

이전 단계에서의 부분합이 3이었기 때문에 end를 1 증가시킨다. 현재 부분합이 5이므로 하나의 경우를 찾은 것이다. 따라서 카운트한다.

 

step 6

이전 단계에서의 부분합이 5였기 때문에 start를 1 증가시킨다. 현재 부분합은 2이므로 무시한다.

 

step 7

이전 단계에서의 부분합이 2였기 때문에 end를 1 증가시킨다. 현재 부분합은 7이므로 무시한다.

 

step 8

이전 단계에서의 부분합이 7이었기 떄문에 start를 1 증가시킨다. 현재 부분합은 5이므로 하나의 경우를 찾은 것이다. 따라서 카운트한다.

 

 

결과적으로 카운트된 경우의 수는 3이다. 따라서 부분합이 5가 되는 부분 연속 수열의 개수는 3인 것을 알 수 있다.

 

문제 모음 : https://www.acmicpc.net/problemset?sort=ac_desc&algo=80

 

출처 : 이것이 취업을 위한 코딩 테스트다(https://g.co/kgs/cemQ62)