반응형
투포인터 알고리즘은 말 그래도 포인터 두개를 설정하는 알고리즘이다
구간합 구할때도 사용가능하다
예시
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가 더이상 이동불가 하므로 종료
정리
포인터를 두개 설정하고 , 구하려는 값에 따라 포인터를 이동시키며 조건을 만족시키는 답을 구한다
여러 문제에 응용해서 적용가능하다
반응형