[ Algorithm ] 투 포인터 알고리즘

투 포인터 (Two Pointer)

리스트에서 순차적으로 기록하며 처리할 때 두가지 위치(점: point)를지정하여 처리하는 알고리즘이다.

예를 들어 [1, 2, 3, 4, 5, 6, 7, 8, 9] 리스트에서 4, 5, 6, 7, 8 을 말할때 "4에서 8까지의 수" 라고 말한다.

위 예시에서 처럼 4~8까지의 수를 "시작점 4"와 "끝점 8"로 2개의 점으로 데이터의 범위를 특정하여

문제를 처리하는 알고리즘을 뜻한다.

 

투 포인터를 활용하기

부분 연속 수열찾기 문제에서 투 포인터 알고리즘을 활용하여 문제를 해결할 수 있다.

1. 시작점과 끝점이 첫 인덱스 0을 가리키도록 만든다.
2. [현재 부분의 합 S]가 [찾아야할 값 M]과 같다면 카운트에 추가해준다.
3. S가 M보다 작거나 같으면 끝점을 1 증가시켜준다.
4. S가 M보다 크면 시작점을 1증가시킨다.
5. 모든 경우를 2번~ 5번까지의 과정을 반복하며 값을 얻는다.

 

투 포인터를 활용한 예시문제

• 데이터의 갯수 N이 8로 주어진다.
• 찾고자하는 부분 합 M이 5로 주어진다.
• 주어지는 수열은 [3, 2, 1, 4, 2, 1, 1, 5] 이다.
• 부분 수열의 합이 M이되는 경우의 개수를 출력하시오.

let n = 8;
let m = 5;
let data = [3, 2, 1, 4, 2, 1, 1, 5];
let cnt = 0;
let intervalSum = 0;
let end = 0;
// start를 순차적으로 증가시키며 반복한다.
for (let start = 0; start < n; start++) {
  // end를 조건에 맞는경우 가능한 만큼 이동시키기
  while (intervalSum < m && end < n) {
    intervalSum += data[end];
    end += 1;
  }
  // 부분합이 m일 때 카운트++
  if (intervalSum == m) cnt += 1;
  intervalSum -= data[start];
}
console.log(cnt); // output: 3

 

마치며...

평소에 코딩테스트를 한번씩 풀어보는데 나도 모르는 사이에 투포인터 알고리즘을 사용하는 경우가 종종 있었던 것 같다. 확실히 용어를 알고 원리를 제대로 파악하니 좀 더 전략적으로 코드를 작성할 수 있게 된 것 같아 뿌듯했다.