10430_나머지
⭕풀이:
A, B, C = map(int, input().split())
print((A + B) % C)
print(((A % C) + (B % C)) % C)
print((A * B) % C)
print(((A % C) * (B % C)) % C)
2609_최대공약수와 최소공배수
⭕풀이:
import sys
A, B = map(int, sys.stdin.readline().split())
a, b = A, B
while b != 0:
a = a % b
a, b = b, a
print(a) # gcd
print(A * B // a) # lcm📌필요지식
1) 유클리드 호제법
- 유클리드 호제법은 최대공약수(GCD : Greatest Common Divisor)와 최소공배수(LCM : Least Common Multiple)를 쉽게 구할 수 있는 알고리즘 중의 하나입니다.
이 알고리즘은 식을 간결하게 해줄 수 있습니다.
1-1) 최대공배수, GCD
예를 들어, a와 b(a>b)가 있다고 할 때,
a와 b의 최대공약수 GCD = b와 a%b(a를 b로 나눈 나머지)의 최대공약수 GCD
gcd(24, 18) = gcd(18, 6) = gcd(6, 0)
여기서 b가 0이 되는 순간의 6이 바로 최대공약수가 됩니다.
1-2) 최소공배수, LCM
- 이렇게 최대공약수를 쉽게 구하면, 최소공배수는 바로 구할 수 있습니다.
두 수 A와 B가 있다고 할 때,A와 B는 각각 x gcd(A, B), y gcd(A, B)입니다.
따라서 A * B / gcd(A, B)는 최소공배수가 됩니다.
1934_최소공배수
⭕풀이:
import sys
test_case = int(input())
for i in range(test_case):
A, B = map(int, sys.stdin.readline().strip().split())
a, b = A, B
while b != 0:
a = a % b
a, b = b, a
print(A * B // a) 6588_골드바흐의 추측
⭕풀이:
from sys import stdin
array = [True for i in range(1000001)] #전체 수만큼 True의 리스트를 생성한다.
for i in range(2, 1001): #i를 2부터 +1씩 반복하면서
if array[i]: #array리스트에 값이 존재한다면,
for j in range(i * i, 1000001, i): #i * i(=i의 제곱)에 해당되는 값들을 j에 대입해
array[j] = False #해당 값들을 False로 바꿔 array에서 제거되면 array에 있는 값들은 소수에 해당하는 값만 True 값을 가지고 있기 때문에 array리스트는 자연스레 소수 리스트가 된다.
while True:
n = int(stdin.readline()) #입력값
if n == 0: #입력값이 0이라면,
break #while문을 멈춰라.
for i in range(3, len(array)): #홀수인 소수들의 합을 찾아내야 되기 때문에 3부터 array의 길이만큼 i에 대입해 반복한다.
if array[i] and array[n-i]: #i와 n-i가 소수라면,
print(n, "=", i, "+", n-i)
break📌필요지식
1) 에라토스테네스의 체
- 에라토스테네스가 만들어 낸 소수를 찾는 방법입니다.
array = [True for i in range(하고 싶은 범위)]
for i in range(2, 하고 싶은 범위의 제곱근):
if array[i]:
for k in range(i + i, 하고 싶은 범위, i):
array[k] = False
- 원리는 다음과 같습니다.
1. 전체 수 만큼 True의 리스트를 생성해줍니다.
2. 2부터 +1씩 해주면서 그 배수에 해당하는 값들을 False로 바꿔줍니다.
2) range(a, b, c)
-
for i in range(a, b, c)는 a부터 b-1까지 c만큼 건너뛰는 수를 뜻합니다.
예를 들면range(0, 50, 5) = 0, 5, 10, 15,..45
입니다.
1676_팩토리얼 0의 개수
⭕풀이:
N = int(input())
cnt = 0
while N > 5:
cnt += N // 5
N //= 5 #N=100일 때, 100 // 5 = 20이지만, 100의 인수인 25는 5를 2개 추가로 가지고 있기 때문에, 따로 더 세줘야 한다.
print(cnt)⭕풀이설명:
1) n // 5
- 끝에서부터 0이 아닌 수를 만날 때까지의 0의 개수를 구하는 방법은 1부터 N까지 for문을 통해 돌면서 2와 5의 개수를 카운팅하는 것입니다. 해당 숫자를 소인수분해 했을 때, 2의 개수와 5의 개수 중 작은 것이 그 답입니다. 그 이유는 0의 개수는 곧 *10이 몇 개 있느냐와 같은데, 10은 2와 5의 곱이기 때문입니다.
2004_조합 0의 개수
⭕풀이:
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
def count_number(n, k):
count = 0
while n:
n //= k
count += n
return count
five_count = count_number(N, 5) - count_number(M, 5) - count_number(N - M, 5)
two_count = count_number(N, 2) - count_number(M, 2) - count_number(N - M, 2)
answer = min(five_count, two_count)
print(answer)⭕풀이설명:
1) 이 문제는 nCr 의 뒤에서부터 0이 아닌 수를 만날 때까지의 0의 개수를 구해야 합니다.
nCr 의 최종적인 값은 팩토리얼 형태가 아니므로, 5의 지수만을 고려해서는 안됩니다.
이 경우에는 2의 지수, 5의 지수를 둘다 구해서 둘 중 작은 값을 답으로 취해야합니다.
분자와 분모 각각은 팩토리얼로만 이루어져 있지만, 나눠지면서 2의 지수와 5의 지수의 규칙에 변동이 생기기 때문입니다.
예를 들어, 6C2의 경우 값은 15이고, 3x5, 5의 지수가 2의 지수보다 더 큽니다.
2) nCr = n! / (n-r)! * r! 이라는 공식을 활용합니다.
2의 지수 = n!의 2의 지수 - (n-r)!의 2의 지수 - r!의 2의 지수
5의 지수 = n!의 5의 지수 - (n-r)!의 5의 지수 - r!의 5의 지수
3) 2와 5 짝이 맞아야 10이 되므로 2의 개수와 5의 개수중 더 작은 값이 10의 개수가 됩니다. 2의 지수와 5의 지수 중 작은 값이 답입니다.
