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 이상의 자연..
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..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
