Algorithm/Math

📌 문제 총 N개의 시험장이 있고, 각각의 시험장마다 응시자들이 있다. i번 시험장에 있는 응시자의 수는 Ai명이다. 감독관은 총감독관과 부감독관으로 두 종류가 있다. 총감독관은 한 시험장에서 감시할 수 있는 응시자의 수가 B명이고, 부감독관은 한 시험장에서 감시할 수 있는 응시자의 수가 C명이다. 각각의 시험장에 총감독관은 오직 1명만 있어야 하고, 부감독관은 여러 명 있어도 된다. 각 시험장마다 응시생들을 모두 감시해야 한다. 이때, 필요한 감독관 수의 최솟값을 구하는 프로그램을 작성하시오. 📌 입력 첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다. 셋째 줄에는 B와 C가 주어진..

📌 문제 주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오. 📌 입력 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. 📌 출력 주어진 수들 중 소수의 개수를 출력한다. 📌 문제 풀이 👨‍🏫 접근 에라토스테네스의 체를 사용하여 소수를 쉽게 찾아낼 수 있다. 소수를 찾는 방법에는 여러 가지 방법이 있다. 가장 쉬운 방법은 for문으로 2부터 n까지 탐색해보는 방법이다. def is_prime_number(n): for i in range(2, n): if n % i == 0: return False return True 이 경우 n까지 모두 탐색하는 방법으로 시간복잡도는 O(N)이라고 할 수 있다. 그런..

📌 문제 두 수 a와 b가 주어졌을 때, a와 b의 최소 공배수를 구하는 프로그램을 작성하시오 📌 입력 첫째 줄에 테스트 케이스의 개수 n이 주어진다. 다음 n개 줄에는 a와 b가 주어진다. a와 b사이에는 공백이 하나 이상 있다. 두 수는 백만보다 작거나 같은 자연수이다 📌 출력 각 테스트 케이스에 대해서 입력으로 주어진 두 수의 최소공배수를 출력한다. 📌 문제 풀이 👨‍🏫 접근 최소공배수는 최대공약수를 통해 구할 수 있다. 최대공약수는 둘을 나눌 수 있는 최대한의 공약수로 이 공약수를 사용해서 두 수의 곱을 나누면 최소공배수를 구할 수 있다. 일반적으로 두 개의 수를 곱하면 서로의 공배수가 만들어지는데, 이를 서로 나눌 수 있는 수중에 가장 크고 두 수의 나머지를 만들지 않는 수가 최대공약수이기 때문..

📌 문제 M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오. 📌 입력 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. 📌 출력 한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다. 📌 문제 풀이 👨‍🏫 접근 소수를 2중 for문으로 구하면 O(N2)이 걸리기 때문에 문제의 최댓값인 106을 제곱했을 때 1012이기 때문에 1000초가량 걸린다. 그런데 소수를 구하는 데에 있어서 그 수를 2부터 자기 자신까지 나누는 것이 아니라 자신의 제곱근만큼만 약수를 구하면 된다. 왜냐하면 제곱근 이후로 나누는 수와 몫이 서로 바뀌어 등장하기 때문이다. 예를 들어 16의 약수는 1, 2, 4, 8,..