투 포인터(다중 포인터) 알고리즘

투 포인터(다중 포인터) 알고리즘

• 배열에서 원래 이중 for문으로 O(N^2)에 처리되는 작업을 2개의 포인터의 움직임으로 O(N)에 해결하는 알고리즘
  여기서 포인터는 C언어의 포인터가 아니라 작업을 처리하기 위해 생성한 변수 이름이다. 포인터라는 변수를 두 개 선언해서 투 포인터라고 부른다.
• 시간 복잡도를 줄이는 데에 용이함

예시

문제

N개의 자연수로 구성된 수열이 있을 때, 합이 M인 부분 연속 수열의 개수 구하기. 수행 제한 시간은 O(N)

투 포인터로 해결하는 방법

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

문제에 따라 구현되는 방식이 조금씩 다를 수 있다.

1. 시작점(start)과 끝점(end)이 첫 번째 원소의 인덱스(0)를 가리키도록 한다.

• 현재의 부분합은 1이므로 무시한다.
• 현재 카운트: 0
  

2. 이전 단계에서의 부분합이 1이었기 때문에 end를 1 증가시킨다.

• 현재의 부분합은 3이므로 무시한다.
• 현재 카운트: 0
  

3. 이전 단계에서의 부분합이 3이었기 때문에 end를 1 증가시킨다.

• 현재의 부분합은 6이므로 무시한다.
• 현재 카운트: 0
  

4. 이전 단계에서의 부분합이 6이었기 때문에 start를 1 증가시킨다.

• 현재의 부분합은 5이므로 카운트를 증가시킨다.
• 현재 카운트: 1
  

5. 이전 단계에서의 부분합이 5이었기 때문에 start를 1 증가시킨다.

• 현재의 부분합은 3이므로 무시한다.
• 현재 카운트: 1
  

위 과정을 끝까지 반복하면 된다.

자바스크립트 코드

const n = 5; // 데이터의 개수
const m = 5; // 찾고자 하는 부분합
const arr = [1, 2, 3, 2, 5];
 
let count = 0;
let intervalSum = 0;
let end = 0;
 
// start를 차례대로 증가시키며 반복
for (let start = 0; start < n; start++) {
  // end를 가능한 만큼 이동시키기
  while (intervalSum < m && end < n) {
    intervalSum += arr[end];
    end += 1;
  }
  // 부분합이 m일 때 카운트 증가
  if (intervalSum == m) {
    count += 1;
  }
  intervalSum -= arr[start];
}
console.log(count);

연습문제
백준 실버 4 https://www.acmicpc.net/problem/2003

공통문제
백준 실버 3 https://www.acmicpc.net/problem/28353
or
백준 골드 5 https://www.acmicpc.net/problem/2470

참고: https://velog.io/@onea/JS-%ED%88%AC-%ED%8F%AC%EC%9D%B8%ED%84%B0%EB%8B%A4%EC%A4%91-%ED%8F%AC%EC%9D%B8%ED%84%B0-%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%8C%A8%ED%84%B4

https://sanghee01.tistory.com/111