반응형 알고리즘 테스트58 백준 4948 : 베르트랑 공준 (파이썬) https://www.acmicpc.net/problem/4948 문제 풀이 4948번: 베르트랑 공준베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼www.acmicpc.net 코드 1import sysnums=[]#입력for line in sys.stdin: if int(line.rstrip()) == 0 : break nums.append(int(line.rstrip()))#에라토스테네스 체isPrime = [True if i>1 else False for i in range(max(nums)*2+1) ]for i in range(len(i.. 2022. 1. 26. 백준 1929 : 소수 구하기 (파이썬) 소수 구하기https://www.acmicpc.net/problem/1929 코드m,n = map(int,input().split())isPrime = [True for _ in range(n+1)]isPrime[0]=isPrime[1]= Falsefor num in range(len(isPrime)) : if isPrime[num] : if m해설에라토스테네스의 체를 사용하면 된다! 에라토스테네스의 체는 https://teching.tistory.com/5에 정리해놓았습니다. 에라토스테네스의 체(소수 판별 알고리즘)유명한 소수 개수 찾기 알고리즘 다수의 소수를 찾을때 사용하는 알고리즘으로 하나의 숫자마다 소수인지 판별하는 것보다 효율적이라 많이 사용한다! 소수의 배수는 소수일수가 없다.. 2022. 1. 25. 백준 11653 : 소인수분해 (파이썬) https://www.acmicpc.net/problem/11653 문제풀이 11653번: 소인수분해첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다.www.acmicpc.net 코드n = int(input())while n>1 : for i in range(2,int(n**.5)+1): if n%i == 0 : print(i) n //= i break else : print(n) break풀이 간단하게 2부터 나눠지는지 확인 후 나눠지면 출력해준 뒤 n을 해당 값으로 나눈 뒤 for문을 돌리면 된다.중요한 건 이때도 제곱근까지만 확인하는 것!!그리고 제곱근까지 안 나눠진다면 n값.. 2022. 1. 25. 백준 9020 : 골드바흐의 추측 (파이썬) 문제https://www.acmicpc.net/problem/9020 코드import sysnums = []#입력for _ in range(int(sys.stdin.readline().rstrip())) : nums.append(int(sys.stdin.readline().rstrip()))#에라토스테네스의 체isPrime = [True for i in range(max(nums) + 1)]isPrime[0]=isPrime[1]=Falsefor i in range(2, len(isPrime)) : if isPrime[i]==False : continue else : for j in range(i*2, len(isPrime), i) : isPrime[j] =.. 2022. 1. 25. 백준 1978 : 소수 찾기 (파이썬) https://www.acmicpc.net/problem/1978 문제풀이 1978번: 소수 찾기첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.www.acmicpc.net코드import syssys.stdin.readline()nums = list(map(int,sys.stdin.readline().split()))answer = 0for num in nums : if num == 1 : continue for i in range(2,int(num**.5)+1) : if num%i ==0 : break else : answer +=1print(answer)코드 해설간단하게 각 숫자.. 2022. 1. 25. 백준 1011 : Fly me to the Alpha Centauri (파이썬) 문제https://www.acmicpc.net/problem/1011 문제풀이 코드import sysfor _ in range(int(sys.stdin.readline().rstrip())) : x,y = map(int,sys.stdin.readline().split()) distance = y-x sqrtDistance = distance**.5 movecnt = int(sqrtDistance)*2 - 1 # 거리가 제곱근일 경우 if sqrtDistance%1 == 0 : print(movecnt) # 거리의 제곱근의 소수점 부분이 0.5 이하일 경우 elif sqrtDistance%1 .5 : print(movecnt+2)코.. 2022. 1. 25. 백준 2839 : 설탕 배달(파이썬) https://www.acmicpc.net/problem/2839 문제풀이 2839번: 설탕 배달상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그www.acmicpc.net 코드n = int(input())for big in range(n//5, -1, -1) : if (n-big*5)%3 == 0 : small = (n-big*5)//3 print(big+small) breakelse : print(-1)코드 풀이탐욕법 만으로는 해결할수 없는 경우가 있어서(11kg일경우 단순 탐욕법을 쓰면 5kg - 2 개 후에 1kg이 남아서.. 2022. 1. 24. 백준 2775 - 부녀회장이 될테야(파이썬) 문제 https://www.acmicpc.net/problem/2775 제출 코드import sysdef plusFloor(preFloor): nextFloor = [sum(preFloor[:i + 1]) for i in range(len(preFloor))] return nextFloorfor _ in range(int(sys.stdin.readline().rstrip())): k = int(sys.stdin.readline().rstrip()) n = int(sys.stdin.readline().rstrip()) liveFloor = [i for i in range(1, n + 1)] for _ in range(k): liveFloor = plusFloor.. 2022. 1. 24. 백준 10250 - ACM호텔(파이썬) https://www.acmicpc.net/problem/10250 문제 풀이 10250번: ACM 호텔프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T 개의 테스트 데이터로 이루어져 있는데 T 는 입력의 맨 첫 줄에 주어진다. 각 테스트 데이터는 한 행으로서 H, W, N, 세 정수www.acmicpc.net 내 코드import sysfor _ in range(int(sys.stdin.readline().rstrip())) : h,w,n = map(int, sys.stdin.readline().split()) print(int(f"{(n-1)%h+1}{(n-1)//h+1:02}"))코드 풀이층수 : 처음에는 n% h로 생각을 했는데 이렇게 하면 문제가 발생한다.%연산을 할.. 2022. 1. 23. 이전 1 ··· 3 4 5 6 7 다음 반응형
