1. 문제 1565번: 수학 (acmicpc.net) 1565번: 수학 배열 D와, 배열 M이 주어졌을 때, D에 있는 모든 수의 배수이며, M에 있는 모든 수의 약수인 수의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 2. 풀이 수들의 최소공배수의 배수는, 모든 수들의 공배수이며, 수들의 최대공약수의 약수는, 모든 수들의 공약수이다. M에서 최대공약수를 구한 다음에, 최대공약수의 약수들을 구한다. $O(\sqrt{N})$으로 구할 수 있다. 여기서 set()을 이용해서 중복을 피해준다 다음 D에서 최소공배수를 구해준다. a,b의 최소공배수는 a*b/gcd(a,b)로 구할 수 있 그리고 M에서 구한 약수들이 최소공배수의 배수인지 판단해준다 from sys import stdin de..
1. 문제 11815번: 짝수? 홀수? (acmicpc.net) 11815번: 짝수? 홀수? B를 A로 나누었을 때 나머지가 0 이라면 A는 B의 약수라고 할 수 있다. (A > 0, B > 0) 예를 들면 15 의 약수는 1, 3, 5, 15 이다. 주어진 수가 가지는 약수 개수가 홀수인지 짝수인지 판별해보자. www.acmicpc.net 2. 풀이 소인수분해 해서 (지수+1)의 곱의 합으로 짝수인지 홀수인지 판단해볼라했는데 수가 10의 18제곱까지 있어서 그런지 시간초과 from sys import stdin n = int(stdin.readline()) num_list = list(map(int,stdin.readline().split())) for i in num_list: p = 2 answer..
1. 약수의 개수 자연수 n의 소인수분해가 $$n = p_{1}^{x_{1}}p_{2}^{x_{2}}...p_{k}^{x_{k}}$$라고 한다면, n의 양의 약수의 개수는 $$d(n) = (x_{1}+1)(x_{2}+1)...(x_{k}+1)$$ n을 소인수분해하여, 소인수들의 지수 + 1의 곱의 합이 약수의 개수이다. 1-1) 간단한 증명 왜냐하면 n의 약수는 $p_{1}, p_{2}, ... , p_{k}$들의 곱으로 이루어져 있는데, 각각은 $x_{1}, x_{2}, ... , x_{k}$개씩 사용할 수 있다. 따라서 곱의 법칙에 의해 모든 경우의 수는 $p_{1}, p_{2}, ... , p_{k}$을 각각 (0,1,2,...,$x_{1}$), (0,1,2,...,$x_{2}$), ... , (0..
1. 설명 어떤 자연수 n에 대하여 n = a*b가 되는 두 자연수 a,b를 n의 약수라고 한다. 이러한 a,b는 반드시 존재한다. 최소 (1,n)이 존재한다는 것. n의 약수를 프로그래밍으로 어떻게 구할까? 가장 쉽게 생각하는 방법은 n을 1부터 n까지 각각 나눠보면서 나누어 떨어지는 수를 찾는 것이다. 그런데 n이 너무 크면, 10억만 되어도 너무 오래걸린다는게 문제 ----------------------------------------------------------------------------------------------------------------------- 그런데 n = a*b에서 a,b의 관계를 생각해보면 a > b, a < b, a = b 3가지 경우가 가능하다. 근데 사실 ..
1. 문제 https://programmers.co.kr/learn/courses/30/lessons/42839 코딩테스트 연습 - 소수 찾기 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 programmers.co.kr 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이조각으로 만들 수 있는 소수가 몇개인지 return하도록 solution 함수를 완성해주세요. 2. 제한사항 numbers는 길이 1 이상 7..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
