투 포인터 (Two Pointer)

 투 포인터는 말 그대로 두 개의 포인터를 사용하여 탐색을 수행하는 알고리즘이다. 어떤 특정한 조건을 만족하는 쌍을 구하고자 할 경우, 단순 이중 루프를 이용하여 계산하면 O(N^2) 시간이 걸리는데, 이는 입력값 N이 100000만 넘어가게 되도 100억번을 수행해야 하므로 굉장히 느리다. 이 때 투 포인터 기법을 사용하면 O(N) 시간에 가능하게 된다. 

 투 포인터의 경우 보통 두 가지 경우로 사용할 수 있는데, 한 가지는 한 포인터는 배열의 맨 앞에, 다른 포인터는 배열의 맨 뒤에 위치하고 조건에 따라 점점 중간으로 가는 방식이고, 다른 한 가지는 앞이나 뒤에서 동시에 출발하여 다른 끝까지 도달하는 방식이다.

 

출처 : https://algodaily.com/lessons/using-the-two-pointer-technique

 위 그림의 경우 첫번째 방식인데, 이 때 배열이 반드시 정렬되어 있어야 한다. 보통 오름차순으로 정렬하게 된다. 이 방식의 대표적인 문제는 배열의 두 요소를 더했을 때 M이 나오는 쌍의 개수를 모두 구하는 문제이다. 앞쪽에서 시작하는 포인터를 start, 뒤쪽에서 시작하는 포인터를 end라고 했을 때, 입력 배열 input은 오름차순으로 정렬되어있다.

 만약 input[start] + input[end] > M이라면 숫자가 줄어들어야 한다. 이 때는 end를 1 감소시키면 더한 값이 감소하게 된다. 만약 input[start] + input[end] < M이라면 숫자가 늘어나야 한다. 이 때는 start를 1 증가시키면 더한 값이 증가하게 된다.  이러한 방식으로 동작하기 때문에 반드시 배열이 오름차순으로 정렬되어 있어야 한다.

 초기 상태에서는 start는 인덱스 0을, end는 배열의 마지막 인덱스를 가리키고 있다. 위 그림의 경우 start = 0이고, end = 4이다. M = 12라고 해본다면 1 + 9 = 10이므로 M보다 작기 때문에 start를 1 증가시킨다. 그 다음은 3 + 9 = 12가 되므로 조건을 만족하게 된다. M = 5라고 해본다면 처음에 1 + 9 = 10이므로 M보다 크기 때문에 end를 1 감소시킨다. 그 다음 1 + 8 = 9이기 때문에 역시 M보다 크므로 end를 1 감소시킨다. 마지막으로 1 + 4 = 5는 조건을 만족하게 된다.

 

 이 동작의 조건은 start < end이다. 이 조건이 없다면 start가 end보다 뒤에 가 있게 되고, 같은 쌍을 두번 구하게 된다. 또한 배열 밖을 벗어난 것에 대한 조건이 없으므로 배열 밖으로 나가게 된다. start는 무조건 오른쪽으로 가고, end는 무조건 왼쪽으로 가게 되므로 start < end 라는 조건을 주게 되면 두 포인터가 만나거나 역전하게 되는 경우 종료하게 되므로 쌍을 한번만 구하고 배열 밖으로 벗어나지도 않게 된다.

 이 문제의 경우 각 루프마다 결국 start를 중가시키거나 end를 감소시키게 되므로 최악의 경우에도 배열의 각 요소를 두번씩만 참조하게 된다. 따라서 O(N) 시간이 된다.

 

출처 :&nbsp;https://www.codingninjas.com/codestudio/library/what-is-a-two-pointer-technique

 두번째 방식은 보통 특정 구간의 부분합이 어떤 특정한 수 M을 만족하는 문제에 이용하게 된다. 위 그림의 경우는 배열의 앞쪽에서 두 포인터가 출발하는 모습이다. 이 점에서 슬라이딩 윈도우와 개념이 비슷하지만, 슬라이딩 윈도우의 경우는 마치 창문을 열 때 창문이 변형되지 않는 것처럼 구간이 고정되어있고 그 구간이 옮겨지는 개념이지만, 투 포인터의 경우는 포인터를 사용하기 때문에 구간이 당연히 변형될 수 있다. 첫번째 방식이 start는 반드시 오른쪽으로, end는 왼쪽으로 갔던 것처럼 두번째 방식 역시 가는 방향이 고정되어야 한다. 왼쪽에서 출발하는 경우에는 start, end 모두 오른쪽으로, 오른쪽에서 출발하는 경우에는 둘 다 왼쪽으로만 가야 한다. 

 만약 start부터 end까지의 합이 M보다 작다면, 구간의 합이 커져야 하므로 end를 1 증가시키고 그 인덱스의 요소를 더해준다. 만약 start부터 end까지의 합이 M보다 크다면, 구간의 합이 작아져야 하므로 start 인덱스가 가리키는 요소를 빼주고 start를 1 증가시킨다.

 M = 18인 경우를 생각해보자. start와 end 모두 인덱스 0에서 시작한다. 그 구간에서의 합은 2이므로 end를 1 증가시키고 end + 1이 가리키는 값을 더해준다. 다음으로 합이 6이므로 역시 end를 1 증가시키고 end + 1이 가리키는 값을 더한다. 그 다음에도 12이므로 똑같이 수행한다. 이제 20이 되었고 M보다 크므로 start가 가리키는 값을 빼주고 start를 1 증가시킨다. 이제 구간의 합이 18이 되었으므로 조건을 만족한다.

 주의해야할 점은 start가 오른쪽 끝까지 가지 못하고 루프가 종료되는 경우를 생각해야 한다. 이 때는 루프를 하나 더 만들고 start를 증가시켜가며 배열의 끝에 도달할 때까지 값을 비교해야 한다. 또한 이 경우에도 start가 end를 넘어가면 안된다. 이는 따로 조건을 만들어주어야 한다.

 

 두번째 방식에서도 각 루프마다 start를 증가시키거나 end를 증가시켜야 한다. 최악의 경우는 end 한번 가고 start가 바로 따라오는 방식으로 끝까지 가는 것인데, 이 경우에도 배열의 각 요소를 최대 두번씩만 참조하게 되므로 O(N) 시간이 된다.

 

 처음 투 포인터를 접했을 때는 두번째 방식만을 기억하고 문제에 적용했는데, 루프 안의 조건문들이 복잡해지고 정답을 도출해내지 못했다. 위 두 방식 이외에도 다양한 변형이 있을 수 있다. 투 포인터는 직접 포인터를 조작해야 하므로 조건이 복잡해질수록 배열 밖을 나가거나 무한 루프가 되기 쉽다. 그러므로 종료 조건이 무조건 수행되는지, 포인터가 가야하는 방향으로 잘 가는지, 매 루프마다 무조건 start나 end가 하나는 움직이는지를 반드시 확인해야 한다.