투포인터 - 1

두개의 포인터를 두고 포인터를 움직이면서 탐색하는 방법중 하나

주로 아래 두가지 상황에서 많이 쓰임

1. 특정 조건을 만족하는 두 수

개구간 [s, e] (특히 배열)에서 s는 0, e는 n-1에서 서로 가까워진다.

https://www.acmicpc.net/problem/3273

투포인터의 기본 아이디어는 다음과 같다.

"정렬된 선형 자료구조"이며, "특정 조건을 만족시키는 두수"가 있다면, 그외의 숫자는 만족시킬수 없다이다.

 

예를 들어 아래의 배열에서 더해서 10이 되는 숫자를 찾는다고 쳐보자

[2,1,8,3,7,4]

우리야 눈으로 3과 7, 2와 8이 보이지만 컴퓨터는 그런거 모른다.

저걸 완전탐색으로 찾는다고 생각해보면, 총 15번의 비교가 일어난다. N개의 쌍이 있다면 O(N^2)다.

근데 3과 7, 2와 8을 생각해보자

특정 조건을 만족시키는 두 수중 한수가 정해지면 , 다른 한수도 무조건 고정된다.

2+8이 10이지 8이 7로 바뀌든 9로바뀌든 절대 10이 될 수없다.

따라서, 2와 8을 찾아서 체크했다면, 이제 2와 8이라는 숫자는 더이상 정답이 될수있는 후보에서 "제외"된다.

 

그럼 그 후보를 제외하면 다음은 무엇을 찾아봐야할까?

아무거나 찾는다면 굳이 투포인터를 사용할 일이 없다.

특정 조건을 만족한다면, 한쪽 숫자가 커지면 다른 숫자는 작아져야한다는 것은 자명한 사실이다.

이러한 점에서 착안해서, 숫자를 "정렬해놓고" 가장 큰 숫자와 가장 작은 숫자에 포인터를 둔뒤 두 포인터를 움직이는 방식을 통해서 답을 찾는것이다.

[1,2,3,4,7,8]

처음엔 s는 1, e는 8에 있을 것이다.

1+8은 9이다. 그렇다면 포인터는 어디로움직여야 할까?

8이 더작아지는건 말이안되므로, 1이 더 커져야한다. 

이제 s는 2, e는 8이므로 더하면 10이되므로 한쌍을 찾는다.

찾은 뒤에는 s,e중 편한걸 아무데나 움직이면된다. 둘다 움직이면 안되냐 물어보는데 이경우엔 가능하지만 안되는 유형의 문제가 있으니 통상적으론 하나만 움직인다.

s가 3으로 가면 이제 s+e가 11이되니, e가 7로가서 다시 한쌍을 찾느다.

 

지금 저문제에서는 그냥 완전탐색이 빠르지만, 만약 N이 많아질경우에는 NlogN 정렬알고리즘을 사용하면 시간복잡도가 O(NlogN)으로 줄어든다. 즉, 대부분의 문제에서 투포인터는 시간복잡도를 줄이기 위해 이용하게된다.

참고로 숫자 10을 찾기 위해 양쪽에서 줄어드는 것을 단순히 "10이 되기 위해", 즉 "합을 줄이거나 늘이기 위해"라고 이해하는 것은 좋지 않다. 2가 여러개있는 경우엔 포인터를 움직인다고 합이 바뀌지도 않는다. 숫자에 중점을 두지않고 포인터에 중점을 둬서, "해당 지점을 포함한 이전의 값들은 더이상 답이될 수 없기 떄문에 제외한다"라고 이해하는 것이 좋다.

 

끄적인날짜 : 25.02.17