투 포인터 (two pointer) 알고리즘이란?

투 포인터란?

'투 포인터'라는 기법은 문자열 string 또는 배열 array 기반의 알고리즘 문제에서 자주 사용할 수 있는 효과적인 기법입니다.

 

구체적으로 투 포인터도 여러 가지 방식이 있지만, 대개는 시작점과 끝점 또는 왼쪽 포인터와 오른쪽 포인터 두 지점을 기준으로 하는 문제 풀이 전략으로 볼 수 있습니다.

 

알고리즘 문제를 풀 때, 일반적인 반복문 접근 또는 브루트 포스 방식을 활용하다 보면 타임아웃에 직면하게 되는 경우가 종종 있습니다.

투 포인터 방식을 활용하면 복잡도를  한단계 낮출 수 있습니다. ==> $O(N^k)$ --> $O(N^{k-1})$ 

 

투 포인터는 크게 두가지 방법으로 응용할 수 있습니다.

• 앞쪽 첫번째에서 시작하는 포인터 & 뒤쪽 끝에서 시작하는 포인터  
• 빠른 포인터가 느린 포인터 보다 앞서는 형식

여기서는 양 끝쪽에서 시작하는 방식인 투 포인터에 대해 간략하게 소개하겠습니다.

 

투 포인터 방식은 범위를 좁혀 나가며 문제를 푸는 방식입니다.

일반적으로 양 끝 투 포인터를 활용한다면, 배열이 정렬되어 있을 때 많이 유용합니다.

 

아래 그림은 두 수의 합이 타겟 값과 같은 지를 확인하는 예제 입니다. 

이 방식은 두 개의 이중 for문으로 쉽게 풀릴 수 있으나, $O(N^2)$ 만큼의 시간 복잡도가 걸립니다.

하지만 투 포인터 방식을 활용하면 복잡도와 공간 효율까지 잡을 수 있게 됩니다.

 

1. 주어진 배열을 정렬합니다.
2. 투 포인터는 양쪽 끝에서 각 포인터가 위치하게 됩니다.
3. 두 포인터의 합과 타겟 값을 비교합니다.
   • 두 포인터의 합이 타겟보다 작다면, 왼쪽 포인터의 위치 +1
   • 두 포인터의 합이 타겟보다 크다면, 오른쪽 포인터의 위치 -1
4. 두 포인터의 합이 타겟값과 같으면 종료, 아니면 포인터 이동하면서 반복 진행.