투 포인터

✏️ 투 포인터

• 투 포인터는 배열에서 두개의 포인터를 사용해 원하는 조건을 만족시키는 부분을 찾거나,
  원하는 값을 찾는 기술이다.
  - 이 방식으로 시간복잡도 문제를 해결할 수 있다.
  - 주로 정렬된 배열이나 리스트와 관련된 문제에서 유용하게 사용되는 기술이다.

📍 투포인터 사용 방법

🔗 투 포인터를 사용하는 알고릐즘 문제 예시

• 만약 1 - 15 까지의 값이 들어있는 배열이라고 했을 때 아래와 같은 방식으로 투 포인트 기법을 사용해 해결할 수 있다.
  • 시작은 int sum 에 0번 인덱스 값을 입력하고,
    두 포인터 모두 0번 인덱스에서 시작한다.
  • sum 이 15 보다 작을 경우 end pointer 를 다음 인덱스로 이동시키고,
    그 값을 sum 에 더해준다.
  • sum 이 15 보다 클 경우 start pointer 를 다음 인덱스로 이동시키고,
    그 값을 sum 에서 빼준다.
  • sum 과 15 가 같을경우 count 에 1 을 더해주고 (정답을 찾았다는 뜻),
    end pointer 를 다음 인덱스로 이동시킨다음,
    그 값을 sum 에 더해준다.
• 위 3가지 조건을 두 포인터가 모두 15에 도착할 때 까지 반복해주면 된다.

📍 투 포인터의 시간 복잡도

• 투 포인터의 원리를 살펴보면 결국 두개의 포인터는 0번 인덱스 부터 마지막 인덱스까지 모든 경우의 수를 파악할 수 있게된다.
  • 이 것을 시간복잡도 공식으로 표현하면 2N 으로 표시할 수 있다.
  • 시간 복잡도에서 상수는 의미가 없게 되므로 매우 효율적으로 모든 경우의 수를 확인할 수 있게된다.

📍 투 포인터 주의점

• 합산 하는 변수의 데이터 타입은 long 으로 한다.
• sum 이 큰 경우 합을 먼저 빼고, start 를 다음 칸으로 이동시킨다.
• while 문은 시작과 끝의 합이 같거나 작은 경우로 정한다.