[투 포인터] 정리

[jusung-c]

투 포인터

알고리즘의 핵심은 전체 범위를 다 고려하는 것이 아닌 최소한의 꼭 봐야 하는 범위만 보는 것이다.

정답을 찾기 위해 봐야하는 모든 범위

정답을 위해 꼭 봐야하는 범위

이렇게 꼭 봐야하는 범위만 설정해서 탐색을 하는 것이 목표이다.

모든 범위

• L과 R의 범위 가 1~10이므로 50가지의 경우를 봐야 했다.

정답을 위해 꼭 봐야하는 범위

• (10,10)까지 도달을 할 때 L이 증가하거나 R이 증가하는 것 밖에 할 수 없어서 각각 9번씩 증가할 수 있으므로 18번의 경우만 봐도 정답을 구할 수 있는 것이다.

투 포인터 알고리즘

화살표 두 개에 의미를 부여해 탐색 범위를 압축하는 알고리즘

1. 1차원 배열 위에 2개의 포인터를 만드는 경우

   1. 2개의 포인터가 모두 왼쪽에서 시작해서 같은 방향으로 이동
   2. 2개의 포인터가 양 끝에서 서로를 향해 이동

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

투 포인터 알고리즘 핵심 키워드

• 1차원 배열에서의 “연속 부분 수열” or “순서를 지키며 차례대로” 라는 말이 있으면 투포인터 접근 시도!
  • 연속 부분 수열을 다 보는 것이 아닌 꼭 필요한 부분만 보도록
• 곱의 최소
  • A x B를 최소로 하려면 A가 커지면 B가 작아져야 한다.
  • 이 경우가 위에서 언급한 관찰을 통해서 문제에 등장하는 변수 2개의 값을 투 포인터로 설정하는 경우이다.