[Algorithm] 투 포인터 알고리즘 정리

투 포인터 알고리즘?

알고리즘 문제를 해결할 때, 자주 사용되는 문제 해결 방법이다.

1. 연속된 데이터 구간을 처리 해야 한다.
2. 배열의 특정 연속된 구간을 처리한다.

위와 같은 문제 해결 방법이 필요할 때, 투 포인터 알고리즘을 사용하면 빠르게 처리할 수 있다. (시간 복잡도 : O(n))

설명

1. 문제 예시

특정한 합을 가지는 부분 연속 수열을 구하라.

2. 알고리즘 적용하기

1. 시작점(S)과 끝점(E)이 첫 번째 원소인 0 index를 가리키도록 한다.

2. 현재 부분 합이 M(특정한 합)보다 같다면, 카운트한다.

3. 현재 부분 합이 M보다 작거나 같다면 E를 1 증가시킨다.

4. 현재 부분 합이 M보다 크면 S를 1 증가시킨다.

5. 모든 경우를 확인할 때 까지 2~4를 반복한다.

실제 문제 적용

수열 7, 6, 1, 6, 2, 0, 4, 2 에서 부분 합이 6이 되는 경우의 개수를 구하라

(()=> {
    function solution(m, arr){
        let answer=0;
        let start=end=0;
        let sum = arr[0];


        while(start < arr.length && end < arr.length) {
            if(sum === m) {
                answer++;
            }
            if(sum <= m){
                end++;
                sum += arr[end];
            }
            else if(sum > m) {
                sum-=arr[start];
                start++;
            }
        }

        return answer;
    }
    
    let a=[7, 6, 1, 6, 2, 0, 4, 2];
    console.log(solution(6, a));
})();