문제 https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 설명 자연수가 주어졌을 때, 이 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구해야 한다. 먼저 입력된 수보다 작거나 같은 소수를 구한다. 에라토스테네스의 체를 이용하면 쉽게 구할 수 있다. 소수인 수의 배수만 지우면 나머지는 소수가 된다는 방식이다. 나중에 연속된 소수의 합을 구하기 쉽게 소수인 수만 primeList에 저장해놓는다. boolean[] prime = new boolean[N + 1]; List primeList = new ArrayList(); // 소수는 false로 표시, 0..
문제 https://www.acmicpc.net/problem/2143 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 www.acmicpc.net 설명 A와 B의 임의의 부 배열 두 개의 합을 더해서 T가 되는 모든 부 배열 쌍의 개수를 구해야 한다. 먼저 A와 B의 원소를 저장할 배열인 arrA와 arrB를 만든다. 그 다음, A와 B의 모든 부 배열의 각 원소의 합을 저장할 리스트인 sumA와 sumB를 만든다. 모든 부 배열의 각 원소의 합을 저장 한..
투 포인터 리스트에서 원하는 값을 얻기 위해 두 개의 포인터를 이용해 각 위치를 기록하면서 처리하는 알고리즘이다. 반복문을 사용해 리스트를 단순 탐색하는 것보다 투 포인터를 사용하면 시간 복잡도를 낮출 수 있다. 리스트의 크기가 N일 때, Worst Case일 경우 시간복잡도를 알아보자. 전자의 경우에는 반복문을 N번씩 두번 돌려서 시간복잡도는 \(O(N \times N) = O(N^2)\) 이 된다. 후자의 경우에는 두 포인터가 모두 N번 탐색하여 시간복잡도는 \(O(2N) = O(N)\) 이 된다. 투 포인터는 위의 그림처럼 두 가지 방식으로 쓰인다. 앞에서부터 시작하는 포인터와 끝에서부터 시작하는 포인터가 중간에서 만나는 방식 둘 다 앞에서 시작해서 하나의 포인터가 다른 포인터보다 앞서면서 끝에 도..
문제 https://www.acmicpc.net/problem/2003 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 설명 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구해야 한다. 일일이 부분합을 구해서 문제를 풀기 보다 시간복잡도를 줄이기 위해 투 포인터를 사용해 구한다. 두 개의 포인터를 각각 start와 end로 두고 둘 다 배열의 앞에서 시작한다. 현재 sum이 M보다 크거나 ..
문제 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 설명 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구해야 한다. 일일이 부분합을 다 구해서 문제를 풀면 시간복잡도가 크게 나오기 때문에 투 포인터를 사용해 구한다. 두 개의 포인터를 각각 start와 end로 두고 둘 다 배열의 앞에서 시작한다. 현재 합이 S보다 작으면 현재 end가 가리키는 값을 더하고 end를 하나 전진시킨다..
