[알고리즘] Two Pointer

투 포인터(Two Pointer) 알고리즘이란?

배열이나 리스트 같은 선형 자료구조에서 두 개의 포인터를 사용하여 문제를 해결하는 방식의 알고리즘

알고리즘 동작 방식

1. 초기화: 두 개의 점(포인터)을 배열의 시작과 끝(또는 특정 위치)에 배치. 두 점의 이동 방향은 자유
2. 포인터 이동: 각 점은 특정 조건에 따라 이동.
3. 조건 확인: 이동하면서 개발자의 특정 조건 값의 만족하는 지를 체크.
4. 종료 조건: 포인터가 배열의 끝이나 중간에서 만나면 알고리즘을 종료, 결과 반환.

포인트
순차적으로 두 개의 포인터의 위치를 기록하며 처리

알고리즘 활용해야 할 때

1. 연속 부분수열 문제: 부분수열이란 주어진 수열의 일부 항을 원래 순서대로 나열하여 얻을 수 있는 수의 열
2. 정렬된 배열에서 두 수의 합: 정렬된 배열에서 두 수의 합이 특정 값이 되는 경우를 찾는 문제
3. 특정 합을 가지는 부분 배열 찾기: 배열에서 연속된 부분 배열의 합이 특정 값이 되는 경우를 찾는 문제.
   • 한 포인터는 배열의 시작을, 다른 포인터는 배열의 끝을 가리키며, 합이 조건을 만족할 때까지 두 포인터를 조정.
4. 팰린드롬 문제: 문자열이 팰린드롬인지(앞뒤가 똑같은지) 확인하는 문제.
   • 한 포인터는 문자열의 시작, 다른 포인터는 끝에서 시작해 서로를 향해 이동하며 문자를 비교

문제 예시

연속 부분수열
N개의 수로 이루어진 수열이 주어집니다.
이 수열에서 연속부분수열의 합이 특정숫자 M이 되는 경우가 몇 번 있는지 구하는 프로그램을 작성하세요.
만약 N=8, M=6이고 수열이 다음과 같다면
const arr = [1,2,1,3,1,1,1,2]
합이 6이 되는 연속부분수열은 {2, 1, 3}, {1, 3, 1, 1}, {3, 1, 1, 1}로 총 3가지입니다.

▣ 입력설명
첫째 줄에 N(1≤N≤100,000), M(1≤M≤100,000,000)이 주어진다. 수열의 원소값은 1,000을 넘지 않는 자연수이다.
▣ 출력설명
첫째 줄에 경우의 수를 출력한다.

풀이

function solution(m, arr) {
    let answer = 0, n = arr.length, sum = 0, start = 0;

    for (let end = 0; end < n; end++) {
        sum += arr[end];
        while (sum > m) {
            sum -= arr[start];
            start++;
        }
        if (sum === m) {
            answer++;
        }
    }

    return count;
}

const arr = [1, 2, 1, 3, 1, 1, 1, 2];

console.log(solution(6, arr));

해석

문제는 n개의 배열을 주고 각 요소의 연속부분수열의 합이 m이 되는 경우의 수를 원한다.

이 문제를 풀려면 각 요소들을 순서대로 더해봐야한다.
그리고 순차적으로 돌며 새로운 값으로 초기화해야하기 때문에 함수안에서 for문 이전 함수 스코프로 초기화 해준다.

function solution(m, arr) {
	let answer = 0, n = arr.length, sum = 0, start = 0;
	for (let end = 0; end < n; end++) {
        sum += arr[end];
  ...
}

여기서 중요한 것은 start와 end다.
end라는 배열의 index 값을 순차적으로 더할때까지 for문을 돌리면 arr[0]=1,arr[1]=2... 순으로 더한다.
그리고 for문 안에서 while문으로 sum이 m보다 커질 때까지 sum에 arr[start] 값을 빼주고 start의 index값을 늘리는 것은 end와 start를 index로 하는 값들을 더하고 빼고 같은 방향으로 순차적으로 이동한며 조건을 맞춰야하기 때문이다.

마지막으로 각 요소들을 더하며 그 수가 m과 같으면 answer를 더해줘야 한다.

  if (sum === m) {
            answer++;
        }

그럼 답이 나온다.

정리
1. 각 배열의 start와 end 포인트를 지정해준다. -> 위 코드에선 두 포인트는 같은 곳에 있다.(시작점)
2. 하나의 포인트를 이동하며 순차적으로 sum에 더해준다. -> 위 코드에서 포인트는 end 기준
3. 더한 값(sum)이 m보다 크면 다른 포인트에 값을 빼준다. -> 위 코드에서 포인트 start 기준
4. 조건을 if문이 아닌 while문을 쓴 이유는 arr[start]를 빼도 sum이 m보다 클 수도 있기 때문에 sum이 m보다 크지 않을 때까지 돌려야하기 때문이다.
5. 위 조건이 맞을 때까지 다른 포인트(start)도 이동해간다.
6. 그 과정에서 sum이 m과 같은 경우(===)는 answer을 늘려준다.

결론

투 포인터 알고리즘은 배열에서 순차적인 비교가 필요할 때 유용하다.
알고리즘 문제에서 잘나오진 않는다고 하지만 가끔 나온다고 하니 알아두자.
뭔가 알고리즘 자체는 순차적으로 비교한다는 깔끔한 알고리즘이지만 정리할 때 구구절절 설명하는 느낌이었다. 내 내공이 부족한 거겠지. 더 열심히 하자.