두 포인터 / 투포인터 알고리즘

 

투포인터 알고리즘은 말 그래도 포인터 두개를 설정하는 알고리즘이다

 

구간합 구할때도 사용가능하다

 

예시

 

1 2 3 4 5의 배열이 있을 때 합이 9가 되는 구간을 모두 구하라고 한다면?

 

1. start_pointer와 end_pointer를 설정하고 포인터 둘 다 1에 두고 시작한다 

 

2. 만약 두 포인터가 가리키고 있는 곳 사이의 값들이 9보다 작다면 end_pointer를 한칸 이동시킨다 

-> 그럼 start_pointer는 1, end_pointer는 2를 가리킨다

 

3. 1+2는 3이므로 아직 9보다 작다 -> end_pointer 한칸 이동

 

4. 1+2+3  은 6이므로 -> end_pointer 한칸 뒤로 이동

 

5. 1+2+3+4 는 10이므로 9보다 크다 -> start_pointer 한칸 뒤로 이동 

-> start_pointer는 2, end_pointer는 4를 가리킨다 

 

6. 2+3+4 = 9 이므로 찾으려는 값이다 이때 이 구간을 저장하고 각 포인터를 한칸씩 이동

-> start_pointer는 3, end_pointer는 5를 가리킨다 

 

7. 3+4+5= 12 -> start_pointer 이동

 

8. 4+5 = 9 값 저장  end_pointer가 더이상 이동불가 하므로 종료

 

정리

포인터를 두개 설정하고 , 구하려는 값에 따라 포인터를 이동시키며 조건을 만족시키는 답을 구한다

여러 문제에 응용해서 적용가능하다