지구정복

https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net -문제해설 일반적으로 그냥 반복문돌려서 소수를 찾으려고하면 O(n)의 시간복잡도로 시간초과가 나버린다. 따라서 이보다 시간을 줄일 수 있는 코드가 필요하다. 이때 이용하는 알고리즘이 '에라토스테네스의 체'이다. 간단히 설명하자면 만약 2가 나왔을 때 2를 제외한 2의 배수들은 모두 제거하는 식이다. 2 3 4 5 6 7 8 9 10 11 12 13 14 15가 있을 때 2배수 제거 2 3 5 7 9 11 13 15 다음으로 3의..

https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net -문제해설 1. 나무길이 입력값들을 받을 때 가장 큰 값을 max에 저장시킨다. 입력값들은 arr배열에 저장한다. 2. 이분탐색을 위해 start = 0, end = max로 설정한다. 3. while( start = m이면 mid값이 너무 작아서 나무를 작게 짜른 것이므로 나무를 크게 자르기 위해 start = mid + 1로 start값을 증가시킨다. 4..

https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net -문제해설 처음에 큐를 이용했다가 자바에서는 특정 인덱스의 원소를 출력하는 기능이 없어서 arraylist로 사용했다. arraylist에는 .get( index ) 메소드가 있기 때문이다. 로직은 간단하다. 먼저 입력받을 때 point객체로 입력받는데 point.x는 입력받는 순서, point.y는 중요도를 입력받는다. point.x는 나중에 m값과 비교해서 정답을 출력하기 위해서 필요하다. 그리고..

https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net -문제해설 손으로 직접 다 써봤더니 점화식을 세울 수 있는 규칙을 찾을 수 있었다. 화질이 구려도 알아볼 수는 있으니 ㅎㅎ 맨 위 사진에서보면 일단 n이 1일 때 k이 증가함에 따라 나올 수 있는 개수도 1씩 증가한다. 그리고 k가 1일 때는 무조건 1이다. 나머지의 경우는 만약 ( 4, 3 )을 구한다고하면 ( 4, 2 ) + ( 3, 3 )을 더하면 나오는 것을 알 수 있다. 이를 코드화하면 아래와 같다. -자바 package dp; import java.io.BufferedReader; import java.io.IO..