[Algorithm] 📈 Two Pointer 알고리즘

📘 Two Pointer 알고리즘이란

다음은 Two Pointer의 사전적 정의이다.

두 개의 포인터를 사용해 문제를 해결하는 알고리즘

투 포인터 알고리즘은 리스트나 배열에 접근할 때, 2개의 포인터의 위치를 기록하면서 처리하느 알고리즘이다.
보통 S(Start), E(End)와 같은 방식으로 이름을 붙인다.

다음은 Two Pointer와 관련된 간단한 예시이다.

📖 Two Pointer 예시

Two Pointer와 관련된 간단한 문제를 알아보자

다음과 같이 5개의 재료를 주고, 차가 2라고 하자.
단순하게 이것을 뽑아내기 위해서는 처음 5와 나머지 4개를 비교한 후, 2도 나머지와 비교하는 완전 탐색을 해야한다.

하지만 이 배열을 다음과 같이 정렬을 한 후, S의 값을 증가시키면서 차가 2가 될 때까지 증가시킨다.

이후 차가 2보다 커지면 E의 값을 증가시킨다.

이후 다시 2가되면 이를 반복하면서 찾아내는 방식이다.

이러한 Two Pointer방식은 S가 처음부터 끝까지, E가 처음부터 끝까지 가는 알고리즘이므로 완전탐색의 O(n^2)에 비해 O(2n)정도로 매우 줄어들게 된다.

🔗 관련 예시

tag:Two Pointer

---

개인 공부 기록용 블로그입니다.
틀리거나 오류가 있을 경우 제보해주시면 감사하겠습니다.😁