지구정복

https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net -문제해설 처음에 해시맵 두 개로 풀었는데 다른 분들 풀이를 보니 그냥 배열과 맵을 가지고도 충분히 풀 수 있는 문제였다. 먼저 필요한 거는 book1이란 배열과 book2란 해시맵이다. book1의 인덱스는 입력되는 순서 1부터 26이 되고 각 인덱스의 값은 포켓몬 이름이 된다. book2 해시맵에서는 book1과 반대로 키가 포켓몬 이름이 되고 값이 입력되는 순서가..

https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net -문제해설 처음에 점화식을 잘못 세워서 약간 고생을 했다; 주어진 수를 제곱합으로 만들기 위해 필요한 최소의 제곱합의 개수를 구하는 문제이다. 제곱합의 개수가 담기는 배열을 dp라고 하자. dp[1] = 1이다. 왜냐하면 1을 만들 수 있는 제곱합의 수는 1의 제곱밖에 없기 때문에 개수는 1개이다. 2를 만들기 위한 최소의 제곱합의 개수는 i - j*j = 2 ..

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의..