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. 문제 25632번: 소수 부르기 게임 (acmicpc.net) 25632번: 소수 부르기 게임 용태가 부를 수 있는 소수는 $11, 13, 17$이고, 유진이가 부를 수 있는 소수는 $13, 17, 19$이다. 둘 다 최선을 다해서 플레이한다면 $13 → 17 → 11 → 19$로 진행될 수 있다. 용태가 더 이상 부를 소수가 www.acmicpc.net 2. 풀이1 두 플레이어가 주어진 범위 a,b와 c,d에서 각각 소수를 찾는다 만약 승리를 위해 최선을 다해서 플레이한다면, 어떻게 해야 할까 핵심 규칙은 이미 부른 소수는 부르지 못한다는 것이다 그러므로 상대가 가지고 있는 소수를 내가 먼저 부른다면, 상대가 가지고 있는 소수를 부르지 못하게 하면서 동시에 나는 턴을 넘기므로 매우 유리해진다 따라..
1. 문제 2777번: 숫자 놀이 (acmicpc.net) 2777번: 숫자 놀이 첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 양의 정수 N이 주어진다. (1 7: print(-1) continue else: prime[n] += 1 a,b = divmod(prime[2],3) if b == 2: b = 1 elif a == 2 and b == 0: a = 1 c,d = divmod(prime[3],2) answer = a+b+c+d+prime[5]+prime[7] print(answer) 2와 3의 경우에 2를 3번 곱한 8까지 압축시켜야하고 3의 경우 2번 곱한 9까지 압축시켜야하고 5,7은 그대로 두면 되고 근데 또 압축이 가능한 경우가 2*..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
