파이썬
[백준 파이썬] # 11047 동전 0
Silver II # 11047 동전 0 https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 풀이 N, K = map(int, input().split()) count = 0 coin = [] for i in range(N): A = int(input()) coin.append(A) coin = sorted(coin, reverse=True) for i in coin: count +=..
[백준 파이썬] 소수 문제 유형 정복하기
파이썬 소수문제 정복하기 한 주간 알고리즘 스터디를 진행하면서 소수 문제를 다루었다. 소수가 사용되는 유형을 정리해두면 도움이 될 것 같아서 정리해보았다. 설명하기 쉬운 코드를 위해 유투브 영상을 일부 참고하였다. 성능 비교를 위해서 time을 측정하였고, input에는 동일하게 5를 넣어 비교해보았다. 소수 여부 판별 # chapter 1 # n이 소수인지 아닌지 판별_약수의 개수를 check 하여 판별 n = int(input()) check = 0 for i in range(1, n+1): # n+1 : n까지 포함하기 위해 ; range 범위의 특성 if n%i == 0: check += 1 if check == 2: print('소수') else: print('소수가 아닌 수') # 5 # 소수..
[백준 파이썬] 에라토스테네스의 체
에라토스테네스의 체 스터디를 통해 이해했던 내용을 바탕으로 정리해보았다. 수학적으로 정확하게 풀어냈다기 보단 스스로 이해한 바를 정리한 것으로 참고만 하길 바란다. 합성수 여부 판단 에라스토테네스의 체를 통해 소수와 합성수 여부를 판단할 수 있다. ※ '소수 2개의 곱를 이용해서 합성수를 만들 수 있다' 는 가정에서 시작한다. N = 6일 때(N>1), 6은 합성수에 해당한다. 합성수는 2개의 숫자 곱으로 표현할 수 있다. 이때 작은 수를 K, 큰 수를 L로 둔다. ex) 6 = 2 * 3 $$ 1