투 포인터(Two Pointers) 알고리즘

투 포인터란?

배열에서 원래 이중 for문으로 O(N^2)에 처리되는 작업을 2개의 포인터의 움직임으로 O(N)에 해결하는 알고리즘이다.

여기서 포인터는 C언어의 포인터가 아니라 작업을 처리하기 위해 생성한 변수이다. 포인터라는 변수를 두개를 선언해서 투 포인터라고 부른다.

 

이분탐색 문제를 투 포인터로도 해결 할 수 있다.

완전 탐색 알고리즘으로 하면 O(N^2)의 수행시간이 나오는데, 투포인터로 시간복잡도를 O(N)으로 줄일 수 있다.

 

 

예시

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

 

투 포인터로 문제 해결하는 방법

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

 

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

 

이를 Javascript 코드로 표현하면 다음과 같다.

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);

 

참고자료 : 이것이 코딩테스트다