기맹기 개발 블로그

BOJ 1644 소수의 연속합 난이도 : 골드 3 https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 전략 매번 소수 판별을 하는 것보다 전처리를 하여 N 이하의 소수 목록을 만들어놓는 것이 유리하다. 따라서 에라토스테네스의 체를 이용하여 ArrayList에 소수들을 저장한 뒤에 투 포인터를 사용한 부분합 탐색을 진행했다. 시행착오 N의 최소 범위인 1이 입력되었을 때 빈 ArrayList에 index로 접근하면서 IndexOutOfBoundsException이 발생했다. 따라서 이를 확인하는 코드를 추가하였다. 코드 import java.util.ArrayList;..

BOJ 1806 부분합 난이도 : 골드 4 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 전략 수열의 길이 N이 최대 100,000이므로 당연히 O(N^2)으로 모두 탐색하는 것은 불가능하다. 투 포인터를 이용하여 O(N)에 배열의 연속된 부분합을 탐색할 수 있다. 시행착오 처음에는 하나의 loop 안에서 start와 end를 함께 옮기려고 했는데 조건문이 좀 복잡해진다. 따라서 둘 중 하나(코드에서는 start)를 루프의 기준..