5. 투포인터

정답을 찾기 위해 봐야하는 범위에서

볼 필요 없는 부분을 제외하고 봐야하는 부분만 본다.

 

화살표 두개에 의미를 부여하여 탐색 범위를 압축하는 방법

1. 1차원 배열 위에 2개의 포인터를 만드는 경우
  1.1 2개의 포인터가 왼쪽에서 시작해서 같은 방향
  1.2 2개의 포인터가 양 끝에서 서로를 향해 이동.

2. 관찰을 통해서 문제에 등장하는 변수 2개의 값을 투 포인터로 표현하는 경우

 

 

투포인터는 O(N)으로 확인할 수 있다는 큰 장점이 있다. 

그래서 연속된 부분합에서 어떠한 값을 확인하는데에도 많이 사용된다.

추천 문제)

 - 백준 부분합 https://www.acmicpc.net/problem/1806

-  소수의 연속합 https://www.acmicpc.net/problem/1644

 

 

꿀팁

- 1차원 ㅐ열에서의 "연속 부분 수열" or "순서를 지키며 차례대로"

- 곱의 최소