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

알고리즘 스터디를 하다가 새로운 알고리즘을 발견해서 호다닥 공부해서 정리하는 "아주 주관적인" 글입니다.

🔎투 포인터 알고리즘을 쓰는 이유

완전 탐색을 할 경우 시간초과를 피하기 위해서 쓰는 방법이다.

 

예를 들어서 N칸의 1차원 배열이 있을 때, 모든 경우의 수를 다 테스트 하면 O(N^2)이 된다.

입력인 N의 최대 범위가 너무 크다면 시간초과를 피 할수 없을 것이다.

 

이럴 때 사용하는 알고리즘이 투 포인터 알고리즘이다.

 

우선 해당 알고리즘은 포인터 포인터 2개를 사용한다.

2개의 포인터는  start, end, left, right 와 같은 배열의 시작과 끝을 의미하는 두개의 포인터를 사용한다는 뜻이다.

저는 포인터 2개를 start와 end로 사용하겠습니다.

 

start와 end의 초기값은 모두 0이며, start<=end를 반드시 만족해야 합니다.

 

예시 문제로 설명을 해보겠습니다.

예시 문제는 N개의 1차원 배열에서 M이상의 합을 구할 수 있는 경우의 수를 구하는 문제입니다.

 

아래의 과정은 start가 N인 동안 반복해줍니다.

1.  만약 현재 부분합이 m이상이거나, 이미 e=N이면 s++ (탐색 범위를 감소시킴)
2. 그렇지 않다면 e++ (탐색 범위를 증가시킴)
3. 현재 부분합이 M과 같으면 결과를 증가시킴.

 

예시 진행 과정

우선 저희는 부분합이 5인 경우의 수를 찾아야 합니다.

빨간 화살표가 start, 파란 화살표가 end를 의미합니다.

초기 시작값은 위에서 설명해드린 대로 start=0, end=0입니다.

이때의 부분합인 S=1이 될것입니다.

S가 M보다 작기 때문에 탐색범위를 증가시킵니다.  즉 end를 한 칸 증가시킵니다.

위 그림은 start가 0이고, end가 1인 상황입니다.

S=3입니다.

S가 M보다 작기 때문에 탐색범위를 증가시킵니다. 즉 end를 한 칸 증가시킵니다.

위 그림은 start가 0이고, end가 2인 상황입니다

S=6이 됩니다.

S가 M보다 크기때문에 탐색범위를 감소시킵니다. 즉 start를 한 칸 증가시킵니다.

위 그림은 start가 1이고 end가 2인 상황입니다.

S=5가 됩니다.

S가 M이상이기 때문에 탐색범위를 감소시킵니다. 즉 start를 한 칸 증가시킵니다.

위 그림은 start와 end가 모두 2인 경우입니다.

S=3입니다.

S가 M보다 작기 때문에 탐색범위를 증가시킵니다.(end 한 칸 증가)

위 그림은 start가 2이고, end가 3인경우입니다.

S=7이 됩니다.

S가 M보다 크기 때문에 탐색범위를 감소시킵니다. (start 한 칸 증가)

 

이렇게 쭉쭉 진행하시면 됩니다.

 

이러한 방식으로 즉 투 포인터를 사용해서 모든 경우의수를 구할 수 있냐? 라는 생각이 들것입니다.

우리는 부분합이 M인 경우의 수를 찾는 것입니다. 

그 부분합은 수열로 이어져있어야 합니다.

당연히 M을 넘는다면 앞에서 짜르는것이 당연합니다.

이렇게 M을 넘을때 앞의 범위를 짜르고, M보다 작을때 뒤의 범위를 증가시키면 모든 경우의 수를 다 찾을 수 있습니다.

 

 

⏰시간 복잡도

투 포인터 알고리즘은 매 루프마다 항상 투 포인터 중 하나는 반드시 1씩 증가하고 있고, 각 포인터가 N번 누적 증가해야 알고리즘이 끝난다. 
따라서 각각 배열 끝에 다다르느는데, O(N)이라도 합쳐서 O(N)이 된다.

 

왜 O(N)이냐?

start와 end중 하나는 매 과정에서 무조건 1씩 증가한다. s와 e는 최대 N까지 증가할 수 있으며, 항상 s<=e이기 때문에 둘이 증가하는 과정은 최대 N번만 반복될 것이다. (N^2 을 넘을수가 없음)

따라서 투 포인터 알고리즘을 사용하면 모든 경우의 수를 비교하는( O(N^2) ) 이 걸리는 문제를 O(N)으로 해결할 수 있다.

 

코드는 간단하게

while문을 돌면서, 만약 start가 n까지 간다면 break시키고,

m을 넘지 않는다면 sum값을 계속 더하고, end값을 증가시켜줍니다.

만약 m을 넘는다면 start가 가르키는 값을 sum에서 빼주면 됩니다.