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

Two Pointer 알고리즘이란,
두 개의 포인터를 조정하면서 정답 조건들을 찾아가는 알고리즘이다.

 

<템플릿>

def two_pointer (array) {
    start, end = 각 포인터 시작 지점;
    /* 순회 배열에 첫 번째 값 넣기 */

    반복문 ( start < start 방향 한계 and end < end 방향 한계 ) {
        If ( /* 포인터들의 이동으로 정답조건이 되었을 경우 */ ) {
            /* 답 갱신 */
            /* start 포인터 지점과 관련한 변수 계산 부분 초기화 */
            /* start 포인터 증가 */
        } else { /* 포인터들의 이동으로 정답조건이 되지 않았을 경우 */
        	/* end 포인터 증가와 end 포인터 증가로 인해 index 예외처리 */
            /* end 포인터 지점과 관련한 변수 계산 부분 업데이트 */
        }
    }
}

 

이 템플릿에서 주의할 점은 start 와 end 포인터가 보통 0 부터 시작하기 때문에 항상 else 구문부터 시작한다.

end 가 마지막 포인터에 다 다르면 정답조건이 되었는지 비교해야 하는데 그 때에도 순회 배열에 값을 넣고 있다. 그래서 먼저 순회배열에 첫 번째 아이템을 넣고 else 구문에는 end 포인터를 미리 증가하여 2번째 아이템을 넣기 시작해야 end 포인터가 마지막 차례일 때 정답조건이 되었는지 비교할 수 있다.

 

이 템플릿 말고 인덱스를 신경쓰기 싫어 무한 반복문 안에서 break 구문을 써 빠져 나오는 템플릿도 있다.