1. 문제 4375번: 1 (acmicpc.net) 4375번: 1 2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오. www.acmicpc.net 2. 풀이1 문제는 n의 배수인, 1로만 이루어진 수 중에서 자리수가 가장 작은 수를 찾는 문제 아주 단순하게는 n보다 큰 1로만 이루어진 수를 생성한 다음에.. 그 수가 n으로 나누어 떨어지는지 검사해보면 된다 n의 길이를 i라 한 다음에... 1로만 이루어진 길이 i인 수부터 시작해서.. n으로 나누어가지고 가장 먼저 나누어 떨어지는 수를 출력 from sys import stdin while 1: try: n = int(stdin.readline()) i = len..
1. 라그랑주의 네 제곱수 정리 모든 자연수 n은 많아야 음이 아닌 4개의 정수의 제곱수 합으로 표현할 수 있다. $$n = a^{2} + b^{2} + c^{2} + d^{2}$$을 만족하는 0 이상의 정수 a,b,c,d가 존재한다. 증명은 매우 까다롭다.. 너무 길어서 따라하기도 힘들다.. https://jjycjnmath.tistory.com/295 [퍼온글] 라그랑주의 네제곱수 정리(Four Square Theorem)와 그 증명 ※ 출처 - http://kevin0960.tistory.com/ 디오판토스의 저서 '산학'에는 '모든 양의 정수는 네 제곱수의 합으로 표현될 수 있다.' 라는 내용이 담겨 있다. 예를 들어, \[ \begin{aligned} 3 &= 1^2 + 1^2 + 1^2 + 0..
1. 문제1 2553번: 마지막 팩토리얼 수 (acmicpc.net) 2553번: 마지막 팩토리얼 수 첫째 줄에 N이 주어진다. N은 20,000보다 작거나 같은 자연수 이다. www.acmicpc.net 2. 풀이 저번에 풀었던 문제와는 다르게 팩토리얼 계산한 값에서 마지막에서 0이 아닌 처음으로 다른 수가 나올때, 그 수를 출력하는 문제 쉽게 생각할 수 있는 방법은..? 저번에 배운 마지막에 0이 나오는 개수를 구하는 방법을 응용하기 마지막에 나오는 0의 개수 k를 구하고, n!을 계산하여 prod라고 저장한 다음에... prod를 $10^{k}$로 나눠준다면? 일의 자리가 정답이 된다 일의 자리는 어떻게 구해? str()로 바꿔서 -1번을 뽑아? 아니 str()로 바꾸는게 생각보다 시간 많이 먹어 ..
1. 문제 1676번: 팩토리얼 0의 개수 (acmicpc.net) 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 2. 풀이 끝에서 0의 개수는 어떻게 세야할까 1000000은 뒤에 0이 6개이기 때문에, $10^{6}$이라고 바로 안다. 이처럼 끝에서 0의 개수가 n개이면, $10^{n}$이라고 바로 알고 있다 다른 수를 예로 들어보면 376129000은 $376129*10^{3}$ 따라서 어떤 수에서 끝의 0의 개수는... 소인수 분해해서 10이 몇개나 있는지 계산하면 될 것이다. 여기서 10은 2와 5의 곱이므로, 소인수분해해서 2와 5의 개수가 몇개나 있는지 계산하면 될 것이다 from..
1. 피사노 주기 피보나치 수열을 자연수 n으로 나눈 나머지가 일정한 주기를 이룬다는 것을 1960년 IBM의 한 직원이 증명했다 예를 들어 0,1로 시작하는 피보나치 수열을 3으로 나눈 나머지는 위와 같이 0,1,1,2,0,2,2,1이 반복된다는 것을 알 수 있다 2. 연습문제 9471번: 피사노 주기 (acmicpc.net) 9471번: 피사노 주기 첫째 줄에 테스트 케이스의 개수 P가 주어진다. 각 테스트 케이스는 N과 M으로 이루어져 있다. N은 테스트 케이스의 번호이고, M은 문제에서 설명한 m이다. www.acmicpc.net 추가로 몇가지 성질이 있다고 제시해주는데 어쨌든 이 문제는 피보나치 수열을 자연수 m으로 나눈 나머지가 주기를 이룬다는 사실을 알고 코딩을 해서 반복되는 수열의 길이를 ..
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 이상의 자연..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
