투 포인터
1. 이중 for문과 유사하지만, 이전의 정보를 활용함으로써 탐색을 줄일 수 있다.
2. 미묘한 인덱스 조절에 따라 오답, 런타임에러 등 많은 결과를 발생시키므로 디테일이 중요하다.
(+ 다른 기법에 비해 문제에 따른 구현법 편차가 크다.)
3. st포인터와 ed포인터가 배열의 끝에 한 번씩 닿는 꼴이 되므로 O(2N) == O(N)이 된다.
(+ 정렬에 O(NlogN) 소모)
4. 종료 조건은 문제에 따라 상이하다. while(st < N), while(ed < N), while(st < ed)...
5. N번째 값에 INF값을 padding함으로써, ed포인터가 끝에 달해도 탐색을 지속해야할 때 경계 조건을 줄일 수 있다.
6. 투 포인터 풀이가 가능한 대부분의 문제는 이분 탐색 풀이가 가능하다.
핵심은, 경계에 달했을 때
st++;
ed = st + 1;
등 과 같이 사용하지 않는 것이다. 이는 이전의 정보를 활용하는 로직을 없애게 된다.
for i = 0 to n:
for j = i + 1 to n:
와 같은 꼴이 되어버림