투 포인터

투포인터

• 다른 용어

  슬라이딩 윈도우 라고도 부름

• 용도

  N칸이 1차원 배열이 있을 때 배열 안의 두 수를 활용한 결과물 들이 원하는 결과물과 같은 것을 찾을 때 사용

  모든 경우의 수를 다 따졌을때 O(N^2) 가 돼서 시간이 길어지는 것을 방지하기 위해 사용

• 조건

  각 원소가 자연수이고 원하는 수 또한 자연수라는 조건이 성립할 때 사용 가능

• 알고리즘 순서

  1. 포인터 두 개를 준비. 시작을 start(s), 끝을 end(e)

  2. 맨 처음에는 start = end = 0, 항상 start<=end 만족

  3. 2개의 포인터는 현재 부분 배열의 시작과 끝을 가리키는 역할.

  s=e일 경우 크기가 0인 아무것도 포함하지 않은 부분 배열.

  다음의 과정을 s < N 번 동안 반복한다

  1. 만약 현재 부분합이 M이상이거나, 이미 e = N 이면 s++

  2. 그렇지 않다면 e++

  3. 현재 부분합이 M과 같다면 결과 ++

• 추가 자료

  그림을 통해 자세하고 알고 싶을시

  https://github.com/WooVictory/Ready-For-Tech-Interview/blob/master/Algorithm/%ED%88%AC%ED%8F%AC%EC%9D%B8%ED%84%B0%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98.md

  참고

요약

• 투포인터는 슬라이딩 윈도우 라고도 부름

• 용도는 모든 경우의 수를 다 세지 않고 (O(N^2)) 원하는 값 찾을 때 사용

• 각 원소가 자연수 이고 원하는 수 또한 자연수라는 조건이 성립할 때 사용 가능.

• 조건에 따라 점진적으로 증가하며 앞 포인터는 끝 포인터를 넘지 않아야 한다.