KEEP CODING

골드바흐의 추측 https://www.acmicpc.net/problem/9020 9020번: 골드바흐의 추측 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아 www.acmicpc.net 에라토스테네스의 체 방법으로 10000까지의 수들 중 소수를 먼저 구하고 시작했다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 max = 10000 numbers = [ True for _ in range(max)] for i in range(2, max): if numbers[i]: for j in range(2*i, max, i): numbe..

베르트랑 공준 https://www.acmicpc.net/problem/4948 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 입력받은 n보다 크고, 2n보다 작거나 같은 수들 중 존재하는 소수의 개수를 출력해야 한다. 작성한 코드(시간: 1168ms) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 max = 123456 def isPrime(num): if num == 1 or num == 0: return False else: for i in range(2,..

소인수분해 https://www.acmicpc.net/problem/11653 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net 시간초과한 경우 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 N = int(input()) numbers = [i for i in range(2, int(N/2)+1)] i = 2 prime = [] while i*i

2581번 - 소수 https://www.acmicpc.net/problem/2581 2581번: 소수 M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다. www.acmicpc.net 내가 작성한 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 M = int(input()) N = int(input()) num = [i for i in range(M, N+1)] prime = [] if num[0] == 1 : num.remove(1) i = 2 while i*i

소수는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수이다. * 1은 소수가 아니다 어떤 수가 소수인지 확인하기 위해서는 n보다 작은 수로 나누어지는지 확인해보면 된다. 2부터 n까지 모두 확인해도 되지만 사실 √ n 까지만 확인하면 된다. 왜냐하면 수가 수를 나누기 위해서는 그 몫이 항상 필요하며, 나누는 수와 몫 중 하나는 반드시 √ n 이하이기 때문이다. √ 108 = 약 10.33이다. 만약 2 ~ √ n 까지 나눠보았는데 나눠지지 않는다면 소수라고 할 수 있다. 1978번 - 소수 찾기 https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의..

Fly me to the Alpha Centauri https://www.acmicpc.net/problem/1011 1011번: Fly me to the Alpha Centauri 우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행 www.acmicpc.net 이동 거리가 계속 변하는 경우라서 어떻게 계산해야 될지 고민했다. 마지막 Y지점에 도착할 때 바로 직전의 이동거리는 1광년이 되어야 한다. 그러기 위해서는 그 전에는 2광년, 또 그 전에는 3광년으로 순차적으로 줄어들어야 한다. 가장 적은 횟수로 이동하기 위해서는 최대로 많이 움직일 수 있는 거리인 k..

부녀회장이 될테야 https://www.acmicpc.net/problem/2775 2775번: 부녀회장이 될테야 첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다 www.acmicpc.net 처음엔 재귀함수로 문제를 해결하려고 했다. 1 2 3 4 5 6 7 8 9 10 11 12 def resident(k, n): if k == 0: return n total = 0 for i in range(1, n+1): total += resident(k-1, i) return total T = int(input()) for _ in range(T): k = int(input()) n = int(input()) pr..

ACM 호텔 https://www.acmicpc.net/problem/10250 10250번: ACM 호텔 프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T 개의 테스트 데이터로 이루어져 있는데 T 는 입력의 맨 첫 줄에 주어진다. 각 테스트 데이터는 한 행으로서 H, W, N, 세 정수 www.acmicpc.net 손님들이 방을 선호하는 기준은 1. 엘리베이터로부터의 거리 2. 층수 이므로 엘리베이터에서 가까운 방부터 배정한다. 1호들부터 101호, 201호, 301호... H01호까지 배정한 후 102호, 202호, 302호... H02호까지 배정한다. 그러므로 객실 배정은 H(호텔의 층 수)와 관련되어있다. H=4, W=4인 호텔에 손님들을 순서대로 배정할경우 다음과 같다. 1번..

달팽이는 올라가고 싶다 https://www.acmicpc.net/problem/2869 2869번: 달팽이는 올라가고 싶다 첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B V에 도달했는지 확인 -> 못미쳤으면 B만큼 내려갔다가 다시 A만큼 올라감 -> V만큼 올라갔는지 확인 을 반복하면 가능하지만 이 문제의 경우, V의 값이 매우 큰 수(1,000,000,000)가 가능하고, 0.15초의 시간제한이 있다. 어떻게 하면 더 빨리 계산이 가능한지 고민했다. 내가 작성한 코드 1 2 3 4 5 6 A, B, V = map(int, input().sp..

그룹단어체커 https://www.acmicpc.net/problem/1316 1316번: 그룹 단어 체커 그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때 www.acmicpc.net 내가 작성한 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 def list_overlap_del(input_list): result_list = [] result_list.append(input_list[0]) for i in range(len(input_list)): if result_list[-1] != ..