[알고리즘] 투 포인터(two pointer)

 

 

언젠가부터 투 포인터는 코딩테스트에서 한 문제씩 나오기 시작했다고 한다.

 

투 포인터는 알고리즘이 적당히 이론적이고,

인덱스 하나 차이로 정답과 런타임 에러를 왔다갔다하기 때문에

구현에서의 디테일이 필요한 알고리즘이다.

 

투 포인터(two pointer)는 배열에서 원래 이중 for문으로 O(N²)에 처리하는 부분을 포인터의 움직임으로 O(N)에 해결하는 알고리즘이다.

C언어에서의 포인터 개념은 아니고, 적당히 커서 정도로 생각하면 된다.

 

이렇게 시간복잡도를 줄일 수 있는 이유는

이중 for문에서 i=0일 때 j=0부터 n-1까지 돌고, i=1일때 j가 0부터 n-1까지 돈다.

이처럼 각 i에 대해서 j가 0부터 n-1까지 도는데,

이 과정에서 i=0일 때 계산하며 얻은 정보가 i=1일 때에 전혀 쓰이지 않는다.

그런데 투 포인터에서는 i =0일 때, 계산하면서 얻은 정보를 i=1일 때 활용한다.

그 정보가 포인터의 이동으로 나타나는 것이다.

 

이분탐색으로 투 포인터 문제를 풀 수 있는 경우가 많다. 반대의 경우도 많으니 참고로 알아두자!

 

그렇다면, 투 포인터는 어떻게 쓰일 수 있을까?

 

먼저, BOJ 2230번: 수 고르기 문제다.

물론, 이분탐색으로도 풀 수 있지만, 직관적으로 떠오르는 for문 풀이로부터 투 포인터 풀이가 어떻게 발전되는지 보자!

이 문제는 이중 for문으로 작성하면 시간초과가 발생한다.

 그런데 가만보면,

첫 번째로 i가 증가함에 따라 a[j] - a[i]가 m 이상이 되는 최초의 지점 j또한 증가한다.

sorting되어있는 배열이므로, 이는 자명하다. 두 번째로 a[j] - a[i]가 m 이상이 되는 최초의 지점 j를 찾은 후에는 a[j+1], a[j+2], ... 을 확인할 필요가 없다는 것도 당연하다. 9-3이 이미 6인데 13-3은 10이므로, 최솟값을 넘어서기 때문이다. 그러면, 문제에서 요구하는게 m이상의 차이 중 최소이기 때문에 j=3,4인 경우에는 확인할 필요가 없는 것이다. 이 두 가지를 바탕으로 O(N²)의 비효율적인 이중 for문 풀이를 투 포인터 풀이를 활용해서 풀 수 있다.

 

 

 변수 st, en을 선언하고, 0에서부터 시작한다. 변수 st는 i와 같은 역할이고, en은 j와 같은 역할이다.

그리고 오른쪽 위에 있는 min은 차이의 최솟값을 저장할 변수이고, 처음에는 아주 큰 값을 두면 된다. INF(0x7fffffff)

 

우리는 각 st에 대해서 a[en] - a[st]가 m이상이 되는 최초의 en을 찾는다.

이 en을 찾으려고 st부터 n-1까지 다 순회하던 중에 이중 for문 방식보다 더 효율적으로 찾아야만 한다.

먼저 맨 처음 할 일은 a[en] - a[st]가 m보다 커질 때까지 en을 증가시켜야한다. 지금은 a[en] - a[st]가 0이니 en을 증가시킨다.

 

 

en을 오른쪽으로 옮기면 a[en] - a[st]는 1이어서 여전히 m보다 작다.

 

 

한 번 더 옮기면 a[en] -a[st]는 7이어서 m이상이 됐고, m이상이 되는 최초의 지점을 찾은 것이다. 이제 min을 7로 갱신하고, en을 더이상 늘리지 않고 st를 옮겨야한다.

 

 

st가 1일 때, a[en] - a[st]가 m 이상이 되는 최초의 지점 en은 바로 그 지점에 있다. 그래서 min을 6으로 바로 갱신한다.

 

 

st는 할 일이 다 끝났으므로, st를 다시 한 칸 옮긴다. 이번에는 a[en] - a[st]가 m보다 작기 때문에 en을 옮긴다.

 

 

en을 한 번더 옮겼는데 m보다 작으므로, 한 번 더 옮긴다.

 

 

 

en을 한 번 더 옮겼더니 a[en] - a[st]가 m 이상이 됐다. 하지만 a[en] - a[st]가 min보다 크기 때문에 min의 갱신은 일어나지 않는다. 이후 과정은 생략한다.

즉, 각 st에 대해 모든 en을 보지 않고, 이전의 en값을 가지고 있으면서 효율적으로 사용하는 것이 투 포인터 이다.

시간 복잡도를 생각하면, 처음 정렬에 O(NlogN)이 쓰일 것이고, 투 포인터를 수행할 때 필요한 시간복잡도를 계산해보면, 한 번 비교를 할 때마다 적어도 st나 en이 한 칸씩 움직인다. 그리고 en이 범위를 벗어나거나 st가 제일 끝에 도달하면 알고리즘이 종료될 것이므로, st와 en이 움직이는 거리는 최대 2N이다. 따라서 O(N)에 해결이 가능하다. 이렇게 이전의 정보를 활용하면, 시간복잡도를 떨굴 수 있다.

 

 투 포인터 알고리즘을 구현할 때 주의할 점이 있다. 인덱스 하나 차이로 인해서 잘못된 참조를 할 수 있다. 0-indexed 기준으로 a[n]은 절대 참조를 해서는 안되는 값이다. 또한 반복문 탈출 조건을 잘못 줘서 en의 값이 n이 된 이후에도 a[en]값을 참조한다던가 하는 일을 저지르기가 쉽다. 주의하도록 하자

 

 

이 글은 바킹독님의 투포인터 자료 및 내용을 참고하였습니다.!