문제 링크 1. 문제 풀이 정수 $n$ 이 최대 $4 \times 10^9$ 일 때, $n$ 보다 크거나 같은 가장 작은 소수를 찾는 문제로 $n$ 이 소수가 아니면 $n + 1$ 을 한 후 소수인지 판정하는 과정을 반복하는 브루트 포스로 찾아나가면 해결할 수 있다. 이때 $n$ 의 제곱근까지만 나누어보는 것으로 소수를 판정하는 계산량을 줄...

문제 링크 1. 문제 풀이 번호가 $1$ 인 포켓몬부터 이름이 주어진 후, 번호가 입력으로 들어오면 포켓몬의 이름을, 이름이 입력으로 들어오면 포켓몬의 번호를 출력하는 문제로 해시맵을 활용하면 간단하게 해결할 수 있다. 포켓몬의 이름은 모두 영어로 되어 있으므로 해시맵에 포켓몬의 이름을 키로, 포켓몬의 번호를 값으로 한 쌍 저장하고, 포켓...

문제 링크 1. 문제 풀이 $6$ 이 적어도 3개 이상 연속으로 포함된 숫자들에 대해 크기 순으로 $N$ 번째 수를 구하는 문제로 $N$ 이 최대 $10,000$ 이라서 브루트 포스로 충분히 해결할 수 있다. $665$ 보다 작은 숫자는 어차피 종말의 수가 될 수 없으니 $666$ 부터 종말의 수인지 $1$ 씩 증가시켜보며 $N$ 번째 종말...

문제 링크 1. 문제 풀이 두 집합 $A$, $B$ 에 대해 $A - B$ 와 $B - A$ 의 합집합인 대칭 차집합을 구하는 문제로 대칭 차집합의 크기는 두 집합의 크기에서 두 집합의 교집합의 크기의 두 배를 빼주면 된다. 2. 코드 1. 풀이 [Java] import java.io.*; import java.util.*; ...

1. 유클리드 호제법 유클리드 호제법(Euclidean Algorithm)은 두 자연수 또는 다항식의 최대공약수(GCD, Greatest Common Divisor)를 구하는 알고리즘의 하나이다. 호제법이란 말은 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는다는 뜻이다. 유클리드 호제법의 기본 원리는 두 자연수(또는 다항식) $...

1. 에라토스테네스의 체 에라토스테네스의 체(Sieve of Eratosthenes)는 고대 그리스 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법으로 $N$ 보다 작거나 같은 모든 소수를 판정할 수 있는 빠르고 쉬운 알고리즘이다. 에라토스테네스의 체는 소수의 배수들은 소수가 아니라는 점을 활용하여 소수가 아닌 수들을 지워가며 최종적으로 소...

문제 링크 1. 문제 풀이 임의의 자연수 $n$ 에 대해 $n$ 보다 크면서 $2n$ 보다 작거나 같은 소수의 개수를 구하는 문제다. 에라토스테네스의 체를 활용하면 효율적으로 해당 구간의 소수의 개수를 셀 수 있다. 2. 코드 1. 풀이 [Java] import java.io.*; import java.util.*; publi...

문제 링크 1. 문제 풀이 주어진 녹색거탑을 내려오는 경우의 수를 구하는 문제로 각 칸에서 아래로 갈 수 있는 칸은 왼쪽, 오른쪽 두 개씩 존재해서 현재 단계까지 올 수 있던 경우의 수가 $n$ 이면 다음 단계까지 갈 수 있는 경우의 수는 $2 \times n$ 이 된다. 즉, $n$ 층짜리 녹색거탑에서 바닥으로 내려오는 경우의 수 $a_n...

문제 링크 1. 문제 풀이 사탕은 $1$ 부터 $1,000,000$ 까지 맛의 점수가 있고 이런 사탕을 사탕상자에 담는 쿼리와 사탕상자에서 꺼내는 쿼리가 주어졌을 때 쿼리들을 해결하는 문제다. $1$ 부터 $1,000,000$ 까지의 수들에 대한 등장 횟수를 세는 세그먼트 트리를 활용하면 해결할 수 있는데 수의 등장 횟수를 저장하는 세그먼트...

문제 링크 1. 문제 풀이 자연수 $N$ 에 대한 가장 작은 생성자를 구하는 문제로 생성자는 해당 숫자와 각 자릿수의 합이 $N$ 이 되는 수들이다. $1$ 부터 $N$ 까지 모든 자연수에 대해 순서대로 분해합을 구해서 $N$ 이 되는지 비교해보면 해결할 수 있다. 자연수 $N$ 의 생성자는 자기 자신과 각 자릿수의 합으로 이루어져서 항상 ...