투 포인터 (Two-Pointer) 알고리즘에 대한 고찰

투포인터 알고리즘

제가 기존에 알고 있는 투포인터 알고리즘은 수열에서 두 수의 합이 특정 값이 되는 두 수의 쌍을 찾는 문제의 해결방법입니다. 이를 간략히 설명해보자면 다음과 같습니다.

• 문제

  길이가 $N$인 정렬된 수열 $\{a_n\}$에서 주어진 $S$에 대해 $a_l + a_r = S$ 를 만족하는 $l, r$을 찾아야 합니다.

• 투포인터 알고리즘

  • 아래 그림과 같이 $l = 1, r = N$ 부터 시작해서 $a_l + a_r$의 값을 $S$와 비교합니다.
    

  • $a_l + a_r$의 값이 $S$보다 작으면 $a_l + a_r$ 의 값을 더 키우기 위해 $l$의 값을 $1$ 증가시킵니다. ($l$ 포인터의 위치를 오른쪽으로 이동)
    

  • $a_l + a_r$의 값이 $S$보다 크면 $a_l + a_r$의 값을 줄이기 위해 $r$의 값을 $1$ 감소시킵니다. ($r$ 포인터의 위치를 왼쪽으로 이동)
    

  • $a_l + a_r$의 값이 $S$가 될 때까지 위의 과정을 반복합니다.

투포인터 알고리즘을 이용하면 수열의 길이 $N$에 대해서 $O(N)$의 시간 복잡도를 가집니다.
수열이 정렬이 되어있지 않다면 정렬을 위해 $O(N log N)$의 시간이 걸리구요.

만약 모든 두 수의 조합을 확인해서 합을 확인한다면 시간복잡도가 ${}_NC_2 \approx O(N^2)$ 이기 때문에 투포인터는 매우 효율적입니다.

의심스러운 투포인터...

전에 잘만 쓰다가 오랜만에 투포인터를 마주치니 뭔가 꺼림칙했습니다.
수열의 모든 두 수의 합을 확인하는 게 아닌데 괜찮나...? 라는 생각이 들었습니다.

예를 들어서 어떤 수열 $\{a_n\}$에서 어떤 두 수를 더해도 $S$가 나오지 않는다고 해봅시다.

이 때 모든 경우의 수에 대해서 확인을 해서 어떤 두 수의 합도 $S$가 되지 않는다는 것을 확인해야 할 거 같은데, 투포인터 방식대로라면 대략 $N$개의 쌍에 대해서만 확인을 하니 투포인터 알고리즘에 대한 확신이 안 들더라구요.

그래서 한 번 이에 대해서 생각해보고 왜 투포인터에서 대략 $N$개의 쌍만 확인해도 나머지 쌍을 확인해보지 않아도 되는지 정리해보았습니다.

괜찮은 이유

아래에서는 수열 $a_n$이 모두 오름차순으로 정렬되어 있다고 가정하고 설명하겠습니다.

$l = 1, r = N$에서부터 시작해 투포인터 알고리즘을 진행해 아래처럼 $l, r$이 위치해있다고 해봅시다.

그리고 $a_l + a_r = S$ 가 되는 $l, r$의 값을 각각 $L, R$이라고 하겠습니다. ($a_L + a_R = S$)

그러면 현재 위치한 $l$ 보다 왼쪽 영역에 있는 값들은 $L$ 이 될 수 없습니다.
반대로 $r$ 보다 오른쪽 영역에 있는 값들은 $R$ 이 될 수 없습니다.

과연 그럴까요? 위에 그림 단계까지 진행된 경우에 $l$ 좌측 영역에 있는 값들 중에서 다른 위치에 있는 수와 더해서 $S$가 나오지 않는다는게 확실한 걸까요?

이를 확인시켜드리겠습니다.

1. $l = 1, r = N$

처음 시작인 $l = 1, r = N$인 경우부터 시작해보겠습니다.

1. 먼저 $a_l + a_r = a_1 + a_N$ 이 $S$ 보다 작은 경우를 생각해보겠습니다.

   여기서 투포인터 알고리즘을 잠깐 잊고 $a_l + a_r$ 이 $S$ 가 아니라는 것이 확실해지는 $(l, r)$ 순서쌍을 찾아서 제외시켜볼게요.

   $a_1 + a_N$ 이 $S$보다 작다는 것이 확인된다면 두 수의 합이 $a_1 + a_N$ 보다 작게 되는 $(l, r)$의 순서쌍은 당연히 그 합이 $S$보다 작게 될테니 저희 탐색 대상에서 제외시켜도 됩니다.

   $a_1 + a_N$ 보다 $a_l + a_r$이 작게 되는 경우는 어떤 경우가 있죠?
   

   $a_1$은 수열 $\{a_n\}$ 중에서 가장 작으니 $r$이 $N$보다 작으면 됩니다. 즉,

   $a_1 + a_2 < a_1 + a_3 < ... < a_1 + a_{N - 1} < a_1 + a_N < S$

   이기 때문에, $(1, 2), (1, 3), ..., (1, N - 1), (1, N)$ 이 제외되면 됩니다. ($l = 1, r = N$도 포함시켰습니다.)

   이 순서쌍들을 유심히 지켜보면 $l = 1$인 순서쌍들을 다 나열한 것임을 확인할 수 있습니다.
   이 뜻은 $l = 1$인 경우에 $a_l + a_r$이 절대 $S$가 될 수 없다는 것을 의미하고, 결론적으로 $l = 1$을 제외하면 된다는 거죠.

   그래서 투포인터 알고리즘에서 $l = 1$에서 오른쪽으로 이동시키면서 $l = 1$을 아예 제외시켜버리는 게 괜찮은 겁니다.

   

2. $a_l + a_r = a_1 + a_N$ 이 $S$ 보다 큰 경우에도 비슷합니다.

   이번에는 $a_1 + a_N$의 값이 $S$ 보다 크기 때문에 위에서 한 것과 비슷하게 $a_1 + a_N$ 보다 큰 값이 되게 하는 $(l, r)$ 순서쌍들은 모두 탈락입니다.

   한번 찾아볼까요?

   

   $S < a_1 + a_N < a_2 + a_N < ... < a_{N-1} + a_N$

   위의 그림과 부등식에서 보듯이 $a_1 + a_N$ 보다 큰 게 확실한 순서쌍들은 $r$은 그대로, $l$ 값이 1보다 큰 순서쌍들입니다.

   다른 순서쌍들도 물론 $a_1 + a_N$보다 클 수도 작을 수도 있지만 확실하지 않죠. 확인이 안 된 순서쌍들입니다.

   나열해보면 $(1, N), (2, N), ..., (N - 2, N), (N - 1, N)$ 입니다. 이는 $r = N$ 인 경우에 가능한 모든 순서쌍이므로 $r = N$ 인 경우는 모두 제외시킬 수 있습니다.

   그래서 $r = N$을 제외시키고 $r = N - 1$로 이동해서 생각할 수 있는 겁니다.

   

2. $l = l', r = r'$

조금 일반적인 경우를 생각해볼게요.

기존의 투포인터 방식으로 $l, r$ 값을 이동시켜서 임의의 $l', r'$에 위치한 경우입니다.

이 때 $l'$ 좌측 영역의 값들은 $L$ 값이 될 수 없고, $r'$ 우측 영역의 값들은 $R$ 값이 될 수 없다는 게 제 주장이었는데 여기서 잠깐만 이게 사실이라고 가정하겠습니다.

여기서 $L, R$ 은 $a_l + a_r = S$ 를 만족시키는 $l, r$ 값을 의미합니다. 즉, $a_L + a_R = S$를 의미합니다.

1. $a_l + a_r = a_{l'} + a_{r'}$ 이 $S$ 보다 작은 경우입니다.

   앞선 설명과 똑같이 진행해볼게요.

   $a_{l'} + a_{r'}$ 보다 합이 작은 $a_l, a_r$ 은 당연히 $S$ 보다도 작기 때문에 제외시켜야 합니다.

   $a_{l'} + a_{r'}$ 보다 작은 게 확실한 $l, r$의 순서쌍은 $l = l'$를 고정하고 $r$값을 $r'$보다 작은 값들입니다.

   

   $a_{l'} + a_{l'+1} < a_{l'} + a_{l'+2} < ... < a_{l'} + a_{r'} < S$

   $l$ 값도 $l'$보다 작아지면 되지만 $l'$보다 작은 값들은 이미 $L$이 될 수 없는 불가능한 값들입니다.

   여기서 $r$ 은 $l'$보다는 커야 합니다. 앞서 말하지는 않았지만 $l, r$의 정의 상 왼쪽 수의 위치가 $l$, 오른쪽 수의 위치가 $r$이기 때문에 $l < r$ 이어야 하기 때문입니다.

   그렇다면 여기서 제외시킬 수 있는 순서쌍을 나열하면 $(l', l' + 1), (l', l' + 2), ..., (l', r' - 1), (l', r')$ 입니다.

   역시 여기서 $l = l'$인 모든 순서쌍에 대해서 항상 두 수의 합이 $S$가 되지 않는다는 것이 확실해지기 때문에 $l = l'$을 제외시킬 수 있습니다.

   그러면 투포인터 알고리즘대로 $l$의 값을 $1$ 증가시켜서 $l = l'$ 인 경우를 모두 제외시킬 수 있게 됩니다. 이제 $l = l' + 1$이 되는거죠.

   여기서 $l = l'$인 모든 순서쌍들 중 앞서 나열되지 않은 $(l', r' + 1), (l', r' + 2), ..., (l', N)$ 들은 $r$ 값이 이미 불가능한 영역에 있기 때문에 이 순서쌍들도 그 합이 $S$가 되지 않는다는 것이 보장됩니다.

   

2. 이제 $a_l + a_r = a_{l'} + a_{r'}$ 이 $S$ 보다 큰 경우입니다.

   $a_{l'} + a_{r'}$ 보다 $a_l + a_r$이 크다면 $a_l + a_r$이 S보다도 크다는 것이기 때문에 제외되어야 합니다.

   $a_{l'} + a_{r'}$ 보다 크려면 $r = r'$로 고정하고 $l$은 $l'$보다 크면 됩니다.

   

   $S < a_{l'} + a_{r'} < a_{l'+1} + a_{r'} < ... < a_{r'-1} + a_{r'}$

   나열해보면 $(l', r'), (l' + 1, r'), ..., (r' - 2, r'), (r' - 1, r')$ 입니다.

   $l'$보다 작은 $l$ 값들은 이미 제외되어 있기 때문에 $r = r'$인 모든 순서쌍을 제외시킬 수 있습니다.

   그래서 $r'$을 제외하고 $r = r' - 1$이 됩니다.

   투포인터 알고리즘대로요.

   

결론

$l = 1, r = N$ 인 경우 (초기 조건)에 $L, R$ 값이 될 수 없는 불가능 영역 ($l = 1$ 또는 $r = N$ 영역)이 생기고,

그 이후에 임의의 $l', r'$ 값에 대해서 좌측, 우측에 불가능한 영역이 있을 때 $l'$ 또는 $r'$ 값이 불가능 영역에 추가되기 때문에 $l$의 좌측 영역, $r$의 우측 영역의 값들은 $L, R$ 값이 될 수 없다는 것이 유지됩니다. (수학적 귀납법)

그래서 수열 $a_n$에 두 수의 합이 $S$가 되는 $a_l, a_r$이 없을 때 위의 방법대로 계속 진행되다보면 아래 그림처럼 $l, r$ 값이 바로 이웃하게 될 때까지 진행이되고 이 마지막 $a_l + a_r$ 이 $S$ 와 같지 않다는 것이 확인이 되면 이때 모든 배열의 두 수의 쌍에 대해서 합이 $S$가 되지 않는다는 것이 확인이 됩니다.

그 이유에 대해 설명해볼게요.

배열에 있는 모든 값의 위치가 우리가 찾는 $L$(또는 $R$)이 될 수 없다는 것을 보이면 되는데요.

$L$을 기준으로 생각해보면,

1. 우선 현재 $l$ 값과 그 좌측 영역에 있는 값들은 우리가 찾고자 하는 $L$ 값이 될 수가 없고,
2. 현재 $r$ 값과 그 우측영역에 있는 값들도 $R$ 값이 될 수 없기 때문에 가능한 $R$ 의 가장 오른쪽 위치는 현재 $l$ 위치입니다. 그런데 $L$은 $R$보다 왼쪽에 있어야하기 때문에 가능한 $R$의 가장 오른쪽 위치보다 오른쪽, 즉 현재 $r$ 의 위치와 그 우측 영역의 값들도 $L$ 이 될 수 없습니다.

위 두 가지로부터 현재 $l$, 현재 $l$의 좌측 영역, 현재 $r$, 현재 $r$ 의 우측 영역 모두 $L$ 이 될 수 없다는 것을 알 수 있습니다.

즉 배열에는 $a_L + a_R = S$ 를 만족하는 $L$ 값이 존재하지 않는다는 거죠. $R$ 도 마찬가지입니다.

소감

투포인터에 대한 의심 때문에 고민하고 나름대로 이해한 내용을 공유해보고자 글을 적어봤습니다. 역시 머릿속에 있는 걸 적으려니 쉽지 않네요 ㅎㅎ