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

불과 물이 서로 도와서 탈출하는 게임!
투 포인터와 비슷한거 같아서 가져왔습니당

📃 예시 문제

[백준] 2467 - 용액

[-99, -2, -1, 4, 98]
이러한 배열이 있다.

간단하게 두 개의 수를 뽑아서 합을 한 값이, 0이랑 가장 가까운 조합을 찾으면 된다.

for (int i = 0; i < N - 1; i++) {
	for (int j = i; j < N; j++) {
    	// 대충 abs() 값이 가장 작은 값 찾는 로직
    }
}   

물론! 이런식으로 해도 답은 나온다.
하지만... O(N^2)이라는 큰 시간복잡도가 나오기 때문에, 시간초과가 발생하게 된다.

📍설명

two pointer (투 포인터)
배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 원하는 값을 찾을 때 까지 탐색하는 알고리즘

일반적으로 정렬이 되어 있어야 사용할 수 있는 알고리즘이다.

슬라이딩 윈도우는 고정된 크기로 창문을 밀듯이 탐색을 하는 반면,
투 포인터는 두개의 포인터가 자유롭게 동적인 크기로 탐색을 진행한다.

위에 문제를 예시로 이미지로 설명을 하겠다.

편의상 왼쪽(빨간색 화살표)을 L,
오른쪽(파란색 화살표)을 R이라고 부르겠다.

L과 R의 합은 -1이다.
그러면... 0과 가까워 질려면 숫자가 커져야 된다.

저 배열은 오름차순으로 정렬되어 있기 때문에, L이 한칸 오른쪽으로 이동하게 되면 L과 R의 합이 커진다.

자 이젠 L과 R의 합은 100이다!
(음? 너무 커졌는데...)

이러면 0보다 크니까... R이 한칸 움직이면 합이 작아진다.

L과 R의 합은 2이다.
아으 아쉽다...

역시 0보다 크니까 R을 한칸 움직여준다.

L과 R의 합은 -3이다.
이번엔 0보다 작으니까 L을 한칸 이동시켜보자.

이런 경우는 더 이상 탐색할 수 없다.

🗂️ 최종 개념 정리

결국 투 포인터는 양쪽에서 조건에 맞게 포인터가 움직인다.

위에 예시코드인 2중 중첩 For문은 O(N^2)이 나오는 반면,
양쪽에서 하나씩... 하나씩... 움직이다가 두 포인터가 만나면 종료하는 투 포인터는 O(N)이라는 시간 복잡도가 나오게 된다.

물론 단점은 존재한다.
배열은 "이분탐색"처럼 무조건 정렬이 되어 있어야 사용할 수 있는 알고리즘이다.