yoo.dev

투포인터 알고리즘이란 주어진 배열에서 연속합을 이용한 문제일때 사용할 수 있는 알고리즘. 보통 연속합으로 가능한 경우의 수를 구하거나, 그 길이를 구하거나 할때 사용된다. (대표문제 참고) 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..

문제 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 풀이 투포인터 알고리즘을 이용해서 풀었다. 배열의 인덱스를 start, end 두 변수에 저장해서 원하는 합보다 sum(arr[start:end])가 작아질 경우엔 end를 하나 증가시키고, 같거나 클 경우엔 start를 하나 증가시킨다. 주의할점은 루프를 끝내는 시점이다. end가 배열의 길이가 되었을때 루프를 멈춰줬더니, start가 이동하면서 하나씩 빼주는 부분이 생략되어 틀린 답이 나왔다. 또 arr[star..