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..

문제 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 풀이 소수 찾기(yuuj.tistory.com/158) + 투포인터 알고리즘(yuuj.tistory.com/160)인 문제. 최소 소수는 2이기 때문에 인풋으로 1이 들어올 경우를 예외처리 안해주면 런타임에러가 난다. import sys # n까지의 소수 리턴 def prime(n): li = [False, False] + [True for _ in range(n-1)] p = [] for i in range(len(li)): if li[i]: p.append(i) for k in range(i+i, len(li), i): li[k] = False return p S = in..