https://www.acmicpc.net/problem/3151 3151번: 합이 0 Elly는 예상치 못하게 프로그래밍 대회를 준비하는 학생들을 가르칠 위기에 처했다. 대회는 정확히 3명으로 구성된 팀만 참가가 가능하다. 그러나 그녀가 가르칠 학생들에게는 큰 문제가 있었다. www.acmicpc.net 풀이1 필요 알고리즘: 이분탐색 "숫자 3개를 합한 값이 0이 된다"라는 것은 \(a+b+c=0\)에서 \(a+b=-c\)임을 의미한다. 따라서 배열을 이중 for문으로 순회하며 \(a+b\)를 찾고, \(a+b=-c\)를 만족하는 \(c\)의 값을 나머지 수에서 이분탐색으로 찾으면 된다. 탐색에 주의할 점으로, \(a+b=-c\)에서 \(c\)가 여러 개 있을 수 있다. 배열이 {-2, -1, 3, ..

https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 풀이 필요 알고리즘: 에라토스테네스의 체, 투 포인터 문제의 요구사항은 연속된 소수의 합으로 자연수 N을 나타낼 수 있는지이다. 이중 for문을 활용하여 \(O(N^{2})\)에 풀 수도 있지만, N의 최댓값 4백만으로는 TLE가 나기 딱 좋으므로 다른 방법을 찾아야 한다. 다행히 연속된 소수의 합이므로 투 포인터로 합계의 범위를 조절하며 확인할 수 있고, 이를 활용하면 \(O(N)\)의 시간 복잡도로 풀 수 있다. 먼저 에라토스테네스의 체를 활용하여 N 이하의 소수를 찾는다. 그 후, 투 포인터 first, las..