SJ_Koding

소수와 결합된 투포인터문제이다. 연속된 수를 찾으므로 두 개의 포인터는 0에서 시작한다고 일반적으로 판단해도 될 것같다. 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 문제 요약: N이 주어졌을 때, 연속된 소수로 이루어진 합의 경우의 수를 찾아라! 3 : 3 (한 가지) 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지) 53 : 5+7+11+13+17 = 53 (두 가지) 20: 7 + 13 은 안됨! 연속된 소수가 아니므로. = 0가지 솔루션: 1. 에라토스테네스의 체로 소수 배열을 만든다. 범위는 최대 400만으로 주어졌다. 일반적인 소수판별(O(N^2))로 구할 수 없다. 2. 두 개의 포인터(..

기업 코딩테스트의 마지막 문제에서 투포인터 문제가 나왔었는데, 종료조건을 건드리다가 시간을 넘겨버렸다. 투포인터의 개념을 이론적으로 알고는 있었지만 실제 투포인터 문제를 풀어본 적은 거의 없다. 이 참에 공부해보자. 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 문제요약 주어진 리스트에서 두 원소의 합이 0과 가장 가까운 원소를 찾는것이다. 원소의 범위는 -10억 ~ 10억 이며, 원소의 개수는 최대 10만개 이므로 모든 경우를 탐색하는 O(N^2)으로 풀어낼 수 없다. 이..