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

투 포인터

투 포인터란, 배열에서 원래 이중 for문으로 O(N^2)으로 처리되는 작업을 2개의 포인터를 통해 O(N)으로 해결해주는 알고리즘입니다.

여기서의 포인터는 C언어에서의 포인터의 개념이 아니라, 해당 지점을 의미하기 위해 사용되는 개념입니다.

 

이중 for문으로 처리할 때 주로 i가 계산되고, 그 안에서 j가 계산되는데, j가 계산될 때 i에 대한 정보가 쓰이지 않습니다.

하지만 투 포인터 같은 경우에는 i에 대한 정보를 사용하여 포인터를 이동시킵니다.

 

투 포인터 문제는 이분 탐색으로도 풀 수 있는 경우가 많고, 그 반대의 경우 또한 많습니다.

투 포인터 문제는 크게 두 가지 유형이 있습니다.

 

1. 정렬 후 양 옆에서 다가오는 것
2. left, right를 지정하고, 상황에 따라 left나 right가 다가오는 것

 

예를 들어 두 수를 합하여 특정한 값을 나타나게 하고자 한다면, 1번의 경우를 사용할 수 있습니다.

배열을 정렬한 뒤, left, right를 지정하고 만약 두 합이 특정한 값보다 작다면 left를 이동시키고, 그다면 right를 이동시켜 특정한 값을 찾는 방법입니다.

 

1번의 경우

배열을 정렬한 뒤에, 양 옆을 left, right로 지정합니다.

9를 찾아야 하는데, 첫 번째 기준으로는 9보다 작기 때문에(1 + 7 = 8), left를 이동합니다.

그 뒤엔 9가 되기 때문에 이후의 처리를 진행해주면 됩니다.

 

 

또 다른 예시로는 부분합을 구할 때는 2번의 경우를 사용할 수 있습니다.

left와 right를 같은 곳에서 시작하여 만약 구하고자 하는 부분합보다 작으면 right를 이동하여 값을 늘려주고,

크다면 left를 이동하여 값을 줄여주면서 부분합을 찾을 수 있습니다.

2번의 경우

left와 right를 지정합니다. 해당 값(5 + 1 = 6)이 원하는 값(15)보다 작기 때문에 right를 이동해줍니다.

원하는 값이 나올 때까지 right를 이동합니다. 그러다가 원하는 값 이상이 되면 left를 이동하면서 최소 길이를 구해줍니다.