💡 투 포인터 (Two Pointers)
👉 배열에서 두 개의 포인터를 사용하여 원하는 결과를 얻는 방법이다.
👉 두 개의 포인터 배치 방법은 아래와 같다.
- 같은 방향에서 시작하는 경우 : 첫 번째 원소에 둘 다 배치한다.
- 서로 다른 방향에서 시작하는 경우 : 첫 번째 원소와 마지막 원소에 배치한다.
👉 다중 for문의 복잡도를 좀 더 선형적으로 풀 수 있다.
💡 투 포인터 예시
👉 아래 배열에서 부분 합이 9가 되는 구간을 찾는 방법
[1, 2, 5, 3, 7, 2, 4, 3, 2]
- 기존 단순 for문 이용 방법
- 0번 인덱스 ~ 0번 + 1 인덱스 값들을 끝까지 더하면서 Target 9가 되는 구간 찾기
- 1번 인덱스 ~ 1번 + 1 인덱스 값들을 끝까지 더하면서 Target 9가 되는 구간 찾기
- 위와 같은 방식으로 마지막 인덱스까지 루프를 돌면서 Target 9가 되는 구간을 찾는다.
-> 알고리즘 시간복잡도 : O(n제곱)
- 투 포인터 방법
- 포인터 P1과 포인터 P2를 지정하고 Target 9 보다 작으면 P1 을 이동하고 더하면서 Target 9가 되는 구간을 찾는다.
- Target 9 보다 크면 P2 를 이동하고 빼면서 구간을 찾는다.
-> 알고리즘 시간복잡도 : O(n)
BE