Algorithms-[Two Pointer]

오늘은 투포인터 알고리즘을 알아볼 것이다.

투포인터 알고리즘은 두개의 포인터(인덱스)를 설정해놓고 위치를 기록하면서 처리하는 알고리즘이다. 이 알고리즘은 문제로 설명하는게 더 빠를 것 같아서 문제로 설명을 해보도록 하겠다. 백준의 수들의 합문제이다.  

1. 우선 시작점(left)과 끝점(right)을 배열의 첫번째를 가리키도록 한다.

2. 구간의 부분합이 목표값(m)과 같다면 저장한다.

3. 현재 부분합이 m보다 작다면 구간을 늘려야 하므로 끝점(right)을 +1 한다.

4. 현재 부분합이 m보다 크거나 같다면 구간을 줄여야 하므로 시작점(left)를 +1 한다.

이렇게 모든 경우를 확인하면 목표값과 같은 경우들이 저장되어있을거고 그중 가작 작은 구간을 포함하면된다. 

내가 얼마전 푼 백준의 부분합 문제는 m이상의 값도 저장하기 때문에 위 설명과에 if문만 손봐주면 동일하게 풀 수 있다.

일반적인 투포인터 문제

2003번: 수들의 합 2

부분합 

1806번: 부분합

https://rebas.kr/765