Two Pointers 투포인터 알고리즘 (연속합 구하기)

투포인터 알고리즘이란 주어진 배열에서 연속합을 이용한 문제일때 사용할 수 있는 알고리즘. 보통 연속합으로 가능한 경우의 수를 구하거나, 그 길이를 구하거나 할때 사용된다. (대표문제 참고) start, end라는 변수를 배열의 인덱스로 사용하며 sum(arr[start:end])을 구하는 방법이다. 처음에 start = end = 0으로 시작하고, start arr[start:end]) 예를들어 배열의 연속합이 S가 되는 경우의 수를 구하는 문제에서는 무한루프를 돌며 sum이 S보다 작은 경우: sum += arr[++end] sum이 S와 같거나 클 경우: sum -= arr[start++] 를 해준 후, 무한루프는 start == end == len(arr)이 되면 빠져나온다. 저장할때는 파이썬의 s..
이론공부 2020. 12. 11. 04:32
1