문제 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 풀이 에라토스테네스의 체를 활용하여 소수 판정을 먼저 수행하고, 투 포인터를 이용하여 합이 입력받은 값이 되는 경우를 세어주면 된다. 에라토스테네스의 체는 범위 내에서 소수의 배수는 모두 지워가며 소수를 구하는 방법이다. 다음의 그림을 보면 쉽게 이해할 수 있다. 먼저 입력받은 범위까지의 소수를 구하고, 그 소수를 리스트에 저장한다. 이 리스트를 시작과 끝을 가리키는 start와 end 포인터를 활용하여 탐색한다. 두 포인터는 초기에 0으로 초기화되며, 두 포인터 사이의 값의 합과 찾으려는 값을 비교하면서 탐색한다. 만약 현재까지의 누적 합이 찾으려는 값보다 작다면 end 포..

문제 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 풀이 시작과 끝을 가리키는 start와 end 포인터를 활용하여 탐색한다. 두 포인터는 초기에 0으로 초기화되며, 두 포인터 사이의 값의 합과 찾으려는 값을 비교하면서 탐색한다. 만약 현재까지의 누적 합이 찾으려는 값보다 작다면 end 포인터를 뒤로 이동시킨다. 만약 end 포인터가 이미 배열의 끝까지 도달했다면 반복문을 종료한다. 누적 합이 찾으려는 값보다 크거나 같다면 현재 구간의 길이를 갱신하고 start 포인터를 뒤로 이동시킨다. 코드..

문제 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 풀이 투 포인터 알고리즘으로 해결할 수 있다. 입력받은 용액을 오름차순으로 정렬한다. 시작과 끝을 가르키는 두 포인터를 선언하여 반복문을 통해 탐색한다. 두 포인터가 가르키는 용액의 합이 0에 가까워질 때마다 결과를 갱신해준다. 만약 합이 0보다 작다면 시작 포인터를 뒤로 움직이고, 0보다 크다면 끝 포인터를 앞으로 움직여준다. 코드 import kotlin.math.* fun main() { val br = System...

문제 2018번: 수들의 합 5 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한 www.acmicpc.net 풀이 투 포인터 알고리즘을 활용하여 해결할 수 있다. 두 개의 포인터 start와 end를 선언하고 초기값을 1과 2로 설정한다. 그리고 start가 end보다 작을 때까지 while문을 실행하며, start부터 end까지의 숫자를 더한 값을 계산한다. 만약 합이 입력받은 값과 같다면 개수를 세어준다. 합이 입력받은 값보다 크다면 start를 움직여 합을 줄이고, 합이 작다면 end를 움직여 합이 크게 해준다. 반복문은 입력받은 숫자의..

문제 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net 풀이 입력받은 수열을 오름차순으로 정렬한 후, 두 포인터를 사용하여 원하는 합을 만드는 투 포인터 문제이다. 앞과 뒤에서 시작하는 두 개의 포인터를 조작하여 합을 조절하며 원하는 값에 도달하는데, 합이 목표값보다 크면 뒤의 포인터를 앞으로, 작으면 앞의 포인터를 뒤로 움직입니다. 두 포인터가 만날 때 반복문을 종료해준다. 투 포인터 알고리즘은 한 번의 루프마다 두 포인터 중 하나만 1씩 증가하며, 각 ..