지구정복

https://www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net -문제해설 처음에 ArrayList에 값을 넣어서 풀었더니 시간초과가 나왔다... 그 다음에는 문제에서 집어넣은 값을 다시 출력하라는 말은 없기 때문에 add되는 값을 배열의 인덱스로 설정해서 풀어보려고 했는데 비트마스크를 이용하면 효율적으로 풀 수 있다는 글을 보았다. 결국 비트마스크를 공부한 뒤 문제를 풀 수 있었다. 비트마스크에 대해 공부한 내용을 간략히 정리하면 이 문제의 경우 입력받은 값을 그대로 출력하라는 조건은 없고 c..

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값과 비교해서 정답을 출력하기 위해서 필요하다. 그리고..