투포인터 알고리즘

투 포인터 알고리즘

• 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하며 처리하는 알고리즘
• 흔히 2, 3, 4, 5, 6, 7번 학생을 지목할 때 간단히 ‘2번부터 7번까지의 학생’이라고 부름
• 리스트에 담긴 데이터에 순차적으로 접근해야 할 때는 시작점과 끝점 2개의 점으로 접근할 때 데이터 범위 표현 가능

전형적인 예시

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

문제) N = 8개의 자연수로 구성된 수열 존재. 합이 M=5인 부분 연속 수열의 개수 구하기

풀이 방식)

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

풀이)

let n = 8; // 데이터의 개수 N
let m = 5; // 찾고자 하는 부분합 M
let data = [3, 2, 4, 1, 2, 2, 1, 5]; // 전체 수열

let cnt = 0;
let intervalSum = 0;
let end = 0;

// start를 차례대로 증가시키며 반복
for (let start = 0; start < n; start += 1) {
  // end를 가능한 만큼 이동
  while (intervalSum < m && end < n) {
    intervalSum += data[end];
    end += 1;
  }
  // 부분합이 m일 떄 카운트 증가
  if ((intervalSum == m)) cnt += 1;
  intervalSum -= data[start];
}
console.log(cnt);