알고리즘/백준 (69) 썸네일형 리스트형 [백준 / 정수론] 14565 : 역원(Inverse) 구하기 (python) 문제 설명 문제 집합 Zn을 0부터 n-1까지의 정수 집합이라고 하자. Zn ∋ a, b, c 일 때, (a+b) mod n = 0이면 b는 a의 덧셈역이라고 하고 (a*c) mod n = 1이면 c는 a의 곱셈역이라고 한다. 정수 N, A가 주어졌을 때 Zn에서의 A의 덧셈역과 곱셈역을 구하시오. 단, 곱셈역을 구할 수 없으면 -1을 출력한다. 입력 첫 번째 줄에 N(2 ≤ N ≤ 10^12)과 A(1 ≤ A < N)이 주어진다. 출력 첫 번째 줄에 A의 N에 대한 덧셈역과 곱셈역을 한 줄에 공백으로 구분하여 출력한다. 예제 입력 1 26 11 예제 출력 1 15 19 예제 입력 2 100 20 예제 출력 2 80 -1 예제 입력 3 32760247633 22801763489 예제 출력 3 995848.. [백준 / 정수론] 11689 : GCD(n, k) = 1 (python) 문제 설명 문제 자연수 n이 주어졌을 때, GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 n (1 ≤ n ≤ 1012)이 주어진다. 출력 GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 출력한다. 예제 입력 1 1 예제 출력 1 1 예제 입력 2 5 예제 출력 2 4 예제 입력 3 10 예제 출력 3 4 예제 입력 4 45 예제 출력 4 24 예제 입력 5 99 예제 출력 5 60 풀이 import math n = int(input()) res = n for i in range(2, int(math.sqrt(n)) + 1): if n % i == 0: res -= res / i while n % i ==.. [백준 / 정수론] 2609 : 최대공약수와 최소공배수 (python) 문제 설명 문제 두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다. 출력 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. 예제 입력 1 24 18 예제 출력 1 6 72 풀이 a, b = map(int, input().split()) def gcd(a, b): if b == 0: return a return gcd (b, a % b) gst = gcd(a, b) lst = a * b // gst print(gst) print(lst) 유클리드 호제법을 사용하여 문제를 해결한다. 유클리드 .. [백준 / 정수론] 1978 : 소수 찾기 (python) 문제 설명 문제 주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오. 입력 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. 출력 주어진 수들 중 소수의 개수를 출력한다. 예제 입력 1 4 1 3 5 7 예제 출력 1 3 풀이 # 소수 찾기 # 에라토스테네스의 체 # n < 1,000 이하의 자연수 import math n = int(input()) num = list(map(int, input().split())) cnt = 0 A = [i for i in range(1001)] A[1] = 0 for i in range(2, int(math.sqrt(len(A)) + 1)): if A[i] == 0:.. [백준 / 소수] 1456 : 거의 소수 (python) 문제 설명 문제 어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다. 두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력한다. 입력 첫째 줄에 왼쪽 범위 A와 오른쪽 범위 B가 공백 한 칸을 사이에 두고 주어진다. 출력 첫째 줄에 총 몇 개가 있는지 출력한다. 제한 1 ≤ A ≤ B ≤ 10^14 예제 입력 1 1 1000 예제 출력 1 25 예제 입력 2 1 10 예제 출력 2 3 예제 입력 3 5324 894739 예제 출력 3 183 풀이 import math A, B = map(int, input().split()) arr = [0] * (int(math.sqrt(B))+1) cnt = 0 for i in range(len(.. [백준 / 그리디] 2839 : 설탕 배달 (python) 문제 설명 문제 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다. 상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다. 상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. (3 ≤ N ≤ 5000) 출력 상근이가 배달하는 봉지의 최소 개수를 출력한다... [백준 / 그리디] 1931 : 회의실 배정 (python) 문제 설명 문제 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다. 입력 첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-.. [백준 / 이진 탐색] 10815 : 숫자 카드 (python) 문제 설명 문제 숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 두 숫자 카드에 같은 수가 적혀있는 경우는 없다. 셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져.. 이전 1 2 3 4 5 6 ··· 9 다음