투 포인터 - Two Pointer

📌 투 포인터 알고리즘 이란?

투 포인터 알고리즘 - $Two$ $Pointer$

❓ 배열에서 어떤 수를 골라서 K 를 만들 수 있는가?

문제에서 특정한 배열이 주어졌을때 두 수의 합,어떤 부분 합이 특정값이 만족하는지 찾는 알고리즘 입니다.

간단하게 이분탐색에서 사용하는 Start 와 End 라는 포인터를 각각 하나씩 가지고
Start 와 End 를 한칸씩 움직이면서 원하는 값을 찾는 방식입니다.

예시로 아래와 같은 배열이 있을때 두 수의합이 14 인 모든 경우를 찾아보겠습니다.

• $[1,3,5,7,9,11,13,15,17,19]$

먼저 Start 는 배열의 시작점, End 는 배열의 끝점을 가르킵니다.

이때 두 포인터의 합이 20이고 원하는 값인 14보다 크기 때문에
End 값을 왼쪽으로 한칸 옮겨보겠습니다.

이번에도 합이 18이기 때문에 계속 End 를 옮겨주겠습니다.

그러면 Start 가 1일때와 End 가 13일때 합이 14로 만족합니다.

만약 투 포인터의 합이 원하는 값 $K$ 보다 크거나 같을때는 Start 값을 옮겨줍니다.

이때 투 포인터의 합은 16이므로 14보다 크기 때문에 다시 End 값을 감소시켜줍니다.

투 포인터가 3과 11이므로 14값을 만족시킵니다.
이 과정을 반복해주면 1,13 | 3,11 | 5,9 총 3가지의 경우의 수가 생깁니다.

즉 포인터 2개를 한칸씩 이동하면서 특정조건에 따라서 옮기면서 모든 경우를 찾는 방법입니다.

📌 투 포인터 코드

start=0
end=len(L)-1

while start<end:

    if L[start]+L[end]==x:
        start+=1
    elif L[start]+L[end]<x:
        start+=1
    else:
        end-=1

📌 투 포인터 시간복잡도

일반적으로 투 포인터는 배열의 모든 경우를 찾기 때문에 $O(N)$ 의 시간 복잡도가 필요합니다. 하지만 대부분의 완전탐색의 경우는 $O(N^2)$ 이거나 그 이상이기 때문에
투 포인터를 사용하면 한번의 탐색으로 모든 경우를 찾을 수 있다는 장점이 있습니다.

📌 투 포인터 전제 조건

투 포인터를 사용하기 위해서는 아래와 같은 전제 조건이 필요합니다.

• 배열은 정렬되어 있는 상태이어야 한다.
• 두개의 포인터를 활용해서 문제에서 주어지는 조건을 만족시킬수 있어야한다.

📌 투 포인터 활용

투 포인터는 이분탐색 , 누적합 알고리즘처럼 아주 다양하게 활용할 수 있습니다.

시작값과 끝값을 굳이 배열의 시작이랑 끝에서 잡지 않아도 되고
투 포인터를 둘다 인덱스 0에서 시작해도 됩니다.

또한 두 수의 합이 아니라 특정 합을 만족하는 연속적인 구간을 구할수도 있고

두 수를 골랐을때 차이가 M 이상이면서 제일 작은 경우 등등 다양하게 활용할 수 있습니다.

또한 투포인터의 코드에서 하나의 수만으로도 특정 조건을 만족시킬 수 있다면
While 문의 조건을 Start<=End 로 잡고 그렇지 않으면 일반적으로 Start<End 로 조건을 잡습니다.

처음에 정의한 투 포인터를 꼭 정의한대로 사용할 필요는없습니다.

단지 두개의 포인터가 있고 그것을 특정조건에 따라 포인터를 한칸씩 이동하면서
문제에서 주어지는 만족하는 해를 구하는 과정 자체가 투 포인터 입니다.

따라서 꼭 두 수의 합을 구할때만이 아니라 배열을 모두 탐색하면서 특정조건을 전부 찾을려고 할때 , 그리고 그것을 두개의 포인터만으로도 탐색가능할때 적절하게 알고리즘을 쓰시면 됩니다.

투 포인터 문제집 - 이 문제집을 풀면서 투 포인터에 대한 감각을 익히시는것을 추천드립니다.