[Algorithm] 투 포인터 알고리즘(Two Pointer Algorithm)

1. 투 포인터 알고리즘

투포인터 알고리즘 or 슬라이딩 윈도우라고 부르며, 배열에 순차적으로 접근해야 할 때 두 개의 점 위치를 기록하며 처리하는 알고리즘이다. 정렬되어 있는 두 리스트 합집합에도 사용된다. 문제 상황에 맞게 투 포인터를 적절히 사용하면 된다. 정확한 사용법은 아래의 예제를 확인해보자.

2. 특정 합을 가지는 부분 연속 수열 찾기 예제

특정 숫자의 배열이 주어질 때, 해당 배열의 연속 수열 합이 특정값을 가지는 것을 확인하는 문제이다. 앞 전에 풀었을땐, 완전 탐색으로 했으나 이번에는 투 포인터 알고리즘을 사용해보았다. 대략적인 순서는 우선 start와 end를 0으로 초기화 한 후, 현재 부분 배열 합이 특정값과 동일하면 count를 하나 올려준다. 그러나, 현재 부분 배열 합이 특정값보다 작으면 end를 하나 증가시키고 특정값보다 크면 start를 하나 증가시킨다. 모든 경우를 확인할때까지 이를 반복하면 된다. 

{2, 4, 5, 3, 8, 1}의 배열을 가지고, 특정 값이 9일때 예시를 들어보자. 

•  start와 end의 인덱스를 0으로 초기화

투포인터의 초기상태이다. 부분 배열의 합은 2로, 조건이 충족하지 않는다. 부분 배열의 합이 특정값보다 작으므로 end를 증가시킨다. 

• 부분 배열합보다 특정값이 크므로 end 증가

다음 부분합은 6으로, 아직 9보다 작아 end를 한번 더 증가시켜 준다. 

• 부분 배열합보다 특정값이 크므로 end 증가

한번 더 end를 옮겨주었다. 이제 합은 11이 되었으며, 특정값보다 크므로 start를 하나 올려준다

• 부분 배열합보다 특정값이 작으므로 start 증가

이제 start를 옮기고 난 후 상태이다. 합은 9가 되었으며, 여기서 특정값과 합이 동일하므로 count를 +1해준다.

이런식으로 반복하여 start와 end가 마지막 인덱스까지 이동할때까지 while문을 진행해주면 된다. 

 

수도코드를 확인해보자. 

input <- start, end, array, M(특정 값)
output <- count

def TwoPointer
    start, end <- 0
    curSum <- 0 // 부분 합
    while ( end <= N ) // N은 배열의 크기
        if (curSum > M)
            curSum -= array[start++]
        else if (curSum < M)
            curSum += array[end++]
        if (curSum == M) count += 1;

 

---

참고문서

https://butter-shower.tistory.com/226

[Algorithm] 투포인터(Two Pointer) 알고리즘

https://ssungkang.tistory.com/entry/Algorithm-Two-Pointers-%ED%88%AC-%ED%8F%AC%EC%9D%B8%ED%84%B0

[Algorithm] Two Pointers, 투 포인터