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

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

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

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

문제 링크 1. 문제 풀이 주어진 녹색거탑을 내려오는 경우의 수를 구하는 문제로 각 칸에서 아래로 갈 수 있는 칸은 왼쪽 오른쪽 두 개씩 존재해서 현재 단계까지 올 수 있던 경우의 수가 $n$ 이면 다음 단계까지 갈 수 있는 경우의 수는 $2 \times n$ 이 된다. 비트 시프트 연산자로 $2$ 의 거듭제곱을 구하는 형태로 해결했다. ...

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

문제 링크 1. 문제 풀이 자연수 $N$ 에 대한 가장 작은 생성자를 구하는 문제로 생성자는 해당 숫자와 각 자릿수의 합이 $N$ 이 되는 수들이다. $1$ 부터 $N$ 까지 모든 자연수에 대해 순서대로 분해합을 구해서 $N$ 이 되는지 비교해보는 브루트 포스로 간단하게 해결할 수 있다. 2. 코드 1. 브루트 포스 [Java] imp...

문제 링크 1. 문제 풀이 듣도 못한 사람의 명단과 보도 못한 사람의 명단에 모두 포함된 사람의 명단을 사전 순으로 출력하는 문제로 두 집합의 교집합을 구하면 되는 간단한 문제다. 2. 코드 1. 집합과 맵 [Java] 듣도 못한 사람은 TreeSet 으로 보도 못한 사람은 HashSet 으로 저장한 후 retainAll 메서드로 두 ...

문제 링크 1. 문제 풀이 각각의 작업들에 대해 머신 $A$ 에서 작업하는 경우랑 머신 $B$ 에서 작업하는 경우랑 완료 시간이 다른데 전체 작업의 완료에 걸리는 최소 시간을 구해야 하는 문제다. 배낭 문제를 활용하면 이 문제를 해결할 수 있는데 배낭의 용량을 머신 $A$ 가 작업을 수행하는데 쓸 수 있는 최대 시간으로 했을 때, 배낭의 가치를...

문제 링크 1. 문제 풀이 짝수 $N$ 에 대해 두 소수의 합으로 나타낼 수 있는 경우의 수를 구하는 문제로 에라토스테네스의 체를 활용해서 $N$ 보다 작은 소수들을 판정해놓으면 간단하게 해결할 수 있다. $2$ 부터 $N / 2$ 까지 탐색하면 순서가 뒤집힌 경우를 세지 않으면서 탐색량도 줄일 수 있다. 2. 코드 1. 에라토스테네스의...