tose33

https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 지금까지의 투포인터 문제랑 같지만, 먼저 소수를 에라토스테네스의 체로 구한 후 투포인터 알고리즘을 적용시키면 된다.

https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 투 포인터 알고리즘으로 합이 s이상이면 합을 감소시키기 위해 left 포인터를 오른쪽으로, s 미만이라면 합을 증가시키기 위해 right를 오른쪽으로 이동하면 된다. 투 포인터 알고리즘에선 항상 포인터를 이동시키고 합을 증감시킬지, 증감 시키고 포인터를 이동할지를 조심해야한다.

https://www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net 오름차순으로 정렬후, left 포인터는 배열의 시작, right 포인터는 = 배열의 마지막으로 한 후 두 값을 더했을때 x와 같다면 카운트 증가시키고 right 포인터 감소 x보다 작다면 left 포인터 증가 x보다 크다면 right 포인터 감소

https://www.acmicpc.net/problem/2559 2559번: 수열 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 www.acmicpc.net 누적합 투 포인터 문제. 오른쪽 포인터는 더하고 왼쪽 포인터는 빼면 O(n) 시간복잡도로 모든 합을 구할수 있다.