투 포인터

1. 투 포인터는 정렬된 상태가 기본이 되어야 한다. 그렇지 않을 경우, 앞뒤의 상관관계가 전혀 없기 때문에 특정 쿼리 후 인덱스 변경에서 논리성이 없어진다.

2. 투 포인터는 같은 지점에서 시작하는 것이 있고, 양끝에서 시작하는 것이 있다. 상황에 맞게 써야하는데, 아직까지는 내가 구분이 정확히 안된다. 구분이 되면 업데이트 할 것.

3. 투 포인터는 인덱스를 옮길 때, 논리적으로 헛점이 없다는 것이 확인되고 난 다음에 쓰는게 맞다.

 

9007 카누선수

중간에서 만나기로 배열을 2개로 만들어준다. 배열을 2개로 만들어 준 다음에 각각 정렬을 하고, 두 포인터로 접근해서 센다. 이 방법은 이분탐색보다 더 빠르게 동작한다. 

 

7453 합이 0인 네 정수

이 문제는 완전탐색으로 풀 경우 4000^4이 되어서 말도 안되는 샘플이 된다. 따라서, 먼저 샘플링을 줄일 필요가 있다. 중간에서 만나기를 시전한다면, 전체 샘플은 4000^2 * 2 수준으로 떨어진다. 3200만개이니 해볼만하다. 이 후, 탐색을 N번 하느냐 LogN번을 하느냐에 따라서 속도가 바뀐다. 여기서 이분탐색으로 Lower, Upper Bound를 찾아서 해결할 수도 있다. 단, 이 경우 TLE가 매우 많이 발생한다.

두 포인터로 0이 되는 경우를 확인할 수 있다. 만약 0보다 크다면 0에 가까워 지기 위해서는 R을 줄여준다. 0보다 작아면 0에 가까워 지기 위해서 L을 올려준다. 0이 된다면, 마찬가지로 Upper, Lower Bound가 있을 수 있기 때문에 두 포인터로 Upper, Lower Bound에 포함되는 값을 센 후에 곱해서 더해준다.

두 포인터의 특성상 끝 부분을 탐색할 때 이런저런 예외 케이스를 처리하기가 굉장히 가다롭다. 여기서 중요한 부분은 L부터 시작하는 부분은 전혀 쓸모없는 -값을 넣어주고, R로 시작하는 부분은 전혀 쓸모없는 +값을 넣어줘서 경계조건을 허물면 코드가 굉장히 간소화된다.