1. 문제 2436번: 공약수 (acmicpc.net) 2436번: 공약수 첫째 줄에 두 개의 자연수가 빈칸을 사이에 두고 주어진다. 첫 번째 수는 어떤 두 개의 자연수의 최대공약수이고, 두 번째 수는 그 자연수들의 최소공배수이다. 입력되는 두 자연수는 2 이상 100,0 www.acmicpc.net 2. 풀이 최대공약수 G, 최소공배수 L이 주어질때 두 수 x,y는 어떻게 구할까 $$x = Gk_{1}$$ $$y = Gk_{2}$$ 이 때 L은 다음과 같이 구할 수 있다 $$L = Gk_{1}k_{2}$$ 따라서 $k_{1}k_{2}$는 L//G로 일정하다. 그러므로 우리는 L//G를 만드는 두 서로소 $k_{1}$과 $k_{2}$를 찾으면 된다. 여기서 $k_{1}$과 $k_{2}$는 1 이상의 자연..
1. 문제 25375번: 아주 간단한 문제 (acmicpc.net) 25375번: 아주 간단한 문제 양의 정수 $a$, $b$가 주어지면, $gcd(x, y) = a$이고 $x + y = b$인 자연수 쌍 $(x, y)$가 존재하는지의 여부를 출력하자. www.acmicpc.net 2. 풀이 gcd(x,y) = a라는 것은 x,y가 a의 배수라는 것이다. ( a >= 1) 즉 x,y는 어떤 자연수 $k_{1}$와 $k_{2}$에 대하여 $$x = ak_{1}$$ $$y = ak_{2}$$ 그러므로 x+y = b를 a로 나눈다면.. $$k_{1} + k_{2} = \frac{b}{a}$$ 여기서 $k_{1}$와 $k_{2}$이 자연수이므로 우변 $\frac{b}{a}$는 자연수이다. 그러므로 자연수 쌍 (..
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. 문제 23888번: 등차수열과 쿼리 (acmicpc.net) 23888번: 등차수열과 쿼리 등차수열은 연속하는 두 항의 차이가 일정한 수열을 뜻한다. 연속한 두 항 중 뒷항에서 앞항을 뺀 값을 공차라고 한다. 초항이 $a$이고 공차가 $d$인 등차수열이 주어진다. 수열의 $i$번째 원소를 www.acmicpc.net 2. 풀이 L번째 항부터 R번째 항까지의 합과 최대공약수를 구하는 문제 등차수열의 합은 초항이 $a_{1}$이고 항 수가 n개이며 공차가 d일때.. $$\frac{n(a_{1} + a_{n})}{2}$$ 등차수열의 일반항은 a + (n-1)d이다. 그러면 L번째 항부터 R번째 항까지의 합은.. 초항이 a + (L-1)d이고 끝 항은 a + (R-1)d이며.. 항 수는 R-L+1개이니까...
1. 문제 1153번: 네 개의 소수 (acmicpc.net) 1153번: 네 개의 소수 임의의 자연수가 주어지면, 이를 네 개의 소수의 합으로 분해하는 프로그램을 작성하시오. 예를 들어 38 = 5 + 7 + 13 + 13이 된다. www.acmicpc.net 임의의 자연수가 소수 4개의 합으로 분해될 수 있는지 구하는 문제 2. 풀이 어떻게 푸는지 모르겠다면.. 브루트 포스로 접근해보는게 가장 현명하다 n이 주어질때 n을 4개의 소수의 합으로 분해하고 싶다면, n보다 작은 소수들로만 분해할 수 있을 것이다 n보다 작은 소수의 리스트를 에라토스테네스의 체로 구하고 이 체에서 4중 for문으로 4개를 선택해서 더해보고 n이 되는지 검사해서 찾기만 하면 바로 break해서 탈출하고 출력해준다 from sy..
1. 팩토리얼의 자리수 $$n! = 1\times2\times...\times n$$로 계산된다. 어떤 정수에 1~9까지 중 하나를 곱하면 자리수가 늘어날수도 있지만, 늘어나지 않을수도 있다 하지만 10 이상을 곱하면 최소한 1자리는 확실히 늘어난다. 이런 통찰에 근거해 10! 이상부터 생각해보면... 10! 이상은 이전 팩토리얼에 10 이상의 수가 계속해서 곱해진다는 특징이 있다 $$11! = 10! \times 11$$$$12! = 11! \times 12$$$$13! = 12! \times 13$$... 그러므로 10! 이상의 팩토리얼은 그 자리수가 유일하게 결정된다. 그 말은 팩토리얼의 자리수를 알면, 몇 팩토리얼인지도 계산이 가능하다. 2. 자리수를 계산하는 방법 123의 자리수는 3자리인데 $..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
