알고리즘 (138) 썸네일형 리스트형 [백준 / 그래프] 20040 : 사이클 게임 (python) 문제 설명 문제 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 번호가 부여된 평면 상의 점 n 개가 주어지며, 이 중 어느 세 점도 일직선 위에 놓이지 않는다. 매 차례 마다 플레이어는 두 점을 선택해서 이를 연결하는 선분을 긋는데, 이전에 그린 선분을 다시 그을 수는 없지만 이미 그린 다른 선분과 교차하는 것은 가능하다. 게임을 진행하다가 처음으로 사이클을 완성하는 순간 게임이 종료된다. 사이클 C는 플레이어가 그린 선분들의 부분집합으로, 다음 조건을 만족한다. C에 속한 임의의 선분의 한 끝점에서 출발하여 모든 선분을 한 번씩만 지나서 출발점으로 되돌아올.. [백준 / 그래프] 1717 : 집합의 표현 (python) 문제 설명 예제 입력 1 7 8 0 1 3 1 1 7 0 7 6 1 7 1 0 3 7 0 4 2 0 1 1 1 1 1 예제 출력 1 NO NO YES parent 배열 초기 상태 1 2 3 4 5 6 7 1 2 3 4 5 6 7 union(1, 3) 1 2 3 4 5 6 7 1 2 1 4 5 6 7 1 1 7 # NO union(7, 6) 1 2 3 4 5 6 7 1 2 1 4 5 7 7 1 7 1 # NO union(3, 7) 1 2 3 4 5 6 7 1 2 1 4 5 7 1 union(4, 2) 1 2 3 4 5 6 7 1 4 1 4 5 7 1 union(1, 1) 1 2 3 4 5 6 7 1 4 1 4 5 7 1 1 1 1 # YES 풀이 import sys input = sys.stdin.read.. [12, 13일차] 07 정수론 함께 푼 문제 [백준 / 정수론] 1978 : 소수 찾기 (python) 문제 설명 문제 주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오. 입력 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1, delicious-kimchi.tistory.com 소수 구하기 [백준 / 정수론] 11689 : GCD(n, k) = 1 (python) 문제 설명 문제 자연수 n이 주어졌을 때, GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 n (1 ≤ n ≤ 1012)이 주어진다. 출력 GCD(n, k) = 1 delicious-kimchi.tistory.com 오일.. [백준 / 정수론] 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(.. 이전 1 2 3 4 5 6 7 ··· 18 다음
