투 포인터 알고리즘 정의, 동작 방법

이것이 코딩테스트다. 나동빈 신님의 강의를 바탕으로 작성하였습니다.

---

투 포인터

"투 포인터 알고리즘"은 '리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하며 처리'하는 알고리즘을 의미한다.
 흔히 2, 3, 4, 5, 7 번 학생을 지목해야 할 때 간단히 '2부터 7번까지의 학생'이라고 부르곤 함.
 리스트에 담긴 데이터에 순차적으로 접근해야 할 때엔 "시작점과 끝점" 2개의 점으로 접근할 데이터의 범위를 표현할 수 있음.

 

대표 예제
 특정한 합을 가지는 부분 연속 수열 찾기. N개의 자연수로 구성된 수열이 있다.
  "합이 M인 부분 연속 수열의 개수"를 구하라. 수행 시간 제한은 O(N)이다 
  [ 1 , 2 , 3, 2, 5] 일 때, M의 합이 5 인 경우는 (2,3), (3,2), (5) 

 

 문제 해결 아이디어 ㅡㅡㅡㅡㅡ
 투 포인터를 활용하여 다음과 같은 알고리즘으로 문제를 해결할 수 있음.
  1. 시작점과 끝점이 첫 번째 원소의 인덱스(0)을 가리키도록 한다.
  2. 현재 부분 합이 M과 같다면, 카운트한다.
  3. 현재 부분 합이 M보다 작다면, end를 1 증가시킴.
  4. 현재 부분 합이 M보다 크거나 같다면, start를 1 증가시킨다. 
  5. 모든 경우를 확인할 때까지 2번부터 4번까지의 과정을 반복한다.

 

 (예) M = 5 // [ 1, 2, 3, 2, 5]
 [초기 단계] 시작점과 끝점이 첫 번째 원소의 인덱스를 가리킴.
  현재의 부분합은 1이므로 무시함.
  
   s    s
 [ 1, 2, 3, 2, 5 ] ->  [ 1, 2, 3, 2, 5 ]
   e       e
  또 다시 현재의 부분합은 3 이므로 무시함.
 
 그 다음 e를 오른쪽으로 이동시키면 부분합은 6이 되므로 무시함.
 단, 부분합이 M값 이상이므로 s를 오른쪽으로 이동시킴.

 이때 부분합을 다시 0부터 갱신시키고, s는 2를 e는 3을 가리키므로 부분합은 5이므로 카운트 증가.
 또한 m값과 동일하거나 클 때 s를 이동시키는데 동일하므로 s를 한칸 이동.
 s와 e가 3을 가리키므로 부분합은 3이므로 무시함.
 결과적으로 카운트는 3이 됨.

 

 

---