2024. 12. 14. 19:12ㆍAlgorithms/백준알고리즘 연습
1934번 최소공배수
로직
1. 구분이 필요한 로직은 첫번째(혹은 두번째) 숫자가 그 다음 숫자의 배수가 될 수 있느냐
2. 없으면 1부터 곱해나가서 매칭되는 숫자가 있느냐
3. 없으면 두수의 곱이 최소 공배수임
초기 코드
import sys
n = int,sys.stdin.readline()
for _ in range(n):
a,b = map(int, sys.stdin.readline().split())
if a % b or b % a == 0 :
larger = max(a,b)
print(larger)
break
for i in range(max(a,b),a*b+1): #최소공배수는두수의곱보다클수없음
if a%i == 0 and b%i ==0,
print(i)
break케이스 별로 나누려다가, 두번째 for문만 있으면 된다는 것을 깨달음
import sys
n = int(sys.stdin.readline())
for _ in range(n):
a,b = map(int, sys.stdin.readline().split())
for i in range(max(a,b),a*b+1): #최소공배수는두수의곱보다클수없음
if i%a == 0 and i%b ==0:
print(i)
시간 초과 됨
숫자가 커지면 for문을 돌리는게 시간복잡도가 a*b만큼 상승함
- Time Complexity: For large numbers, this method can be very slow, potentially taking O(ab) time in the worst case
import sys
def gcd(a, b):
while b:
a, b = b, a % b
return a
n = int(sys.stdin.readline())
for _ in range(n):
a, b = map(int, sys.stdin.readline().split())
lcm = (a * b) // gcd(a, b)
print(lcm)
def gcd(a, b):
while b:
a, b = b, a % b
return a
=> https://en.wikipedia.org/wiki/Euclidean_algorithm
Euclidean algorithm - Wikipedia
From Wikipedia, the free encyclopedia Algorithm for computing greatest common divisors Euclid's method for finding the greatest common divisor (GCD) of two starting lengths BA and DC, both defined to be multiples of a common "unit" length. The length DC be
en.wikipedia.org
- Inside the loop, we perform two operations in a single line:
a, b = b, a % bThis is equivalent to:
temp = b
b = a % b
a = temp - This process continues until b becomes 0.
Example:
Let's find the GCD of 48 and 18:
- a = 48, b = 18
- a = 18, b = 48 % 18 = 12
- a = 12, b = 18 % 12 = 6
- a = 6, b = 12 % 6 = 0
13241번
최소공배수 다국어
| 2 초 | 512 MB | 24924 | 15461 | 14149 | 62.879% |
문제
정수 B에 0보다 큰 정수인 N을 곱해 정수 A를 만들 수 있다면, A는 B의 배수이다.
예:
- 10은 5의 배수이다 (5*2 = 10)
- 10은 10의 배수이다(10*1 = 10)
- 6은 1의 배수이다(1*6 = 6)
- 20은 1, 2, 4,5,10,20의 배수이다.
다른 예:
- 2와 5의 최소공배수는 10이고, 그 이유는 2와 5보다 작은 공배수가 없기 때문이다.
- 10과 20의 최소공배수는 20이다.
- 5와 3의 최소공배수는 15이다.
당신은 두 수에 대하여 최소공배수를 구하는 프로그램을 작성 하는 것이 목표이다.
입력
한 줄에 두 정수 A와 B가 공백으로 분리되어 주어진다.
50%의 입력 중 A와 B는 1000(103)보다 작다. 다른 50%의 입력은 1000보다 크고 100000000(108)보다 작다.
추가: 큰 수 입력에 대하여 변수를 64비트 정수로 선언하시오. C/C++에서는 long long int를 사용하고, Java에서는 long을 사용하시오.
출력
A와 B의 최소공배수를 한 줄에 출력한다.
예제 입력 1 복사
1 1
예제 출력 1 복사
1
예제 입력 2 복사
3 5
예제 출력 2 복사
15
예제 입력 3 복사
1 123
예제 출력 3 복사
123
예제 입력 4 복사
121 199
예제 출력 4 복사
24079
추가: 큰 수 입력에 대하여 변수를 64비트 정수로 선언하시오.
원래 파이선은 64비트 형태로 저장되기 때문에 위의1934번 코드에서 for문만 없애주면 됨
1735번 분수 합
초기 코드
import sys
def gcd(a,b):
while b:
a,b = b, a%b
return a
a,b = map(int, sys.stdin.readline().split())
c,d = map(int, sys.stdin.readline().split())
lcm = (a * b) // gcd(a, b)
c2 = c*(lcm//a) # Changed to integer division
d2 = d*(lcm//b) # Changed to integer division
print(c2+d2, lcm, end=" ")
답안 코드
import sys
def gcd(a, b):
while b:
a, b = b, a % b
return a
# Read input
a, b = map(int, sys.stdin.readline().split())
c, d = map(int, sys.stdin.readline().split())
# Calculate the common denominator (LCM of b and d)
lcm = (b * d) // gcd(b, d)
# Add fractions
numerator = a * (lcm // b) + c * (lcm // d)
# Reduce the fraction
common_divisor = gcd(numerator, lcm)
numerator //= common_divisor
denominator = lcm // common_divisor
# Print result
print(numerator, denominator)
백준 2485번 가로수 ( 다시 풀기 )
로직
1. 주어진 리스트의 숫자에서 앞수에서 뒷수를 뺀 값이 그 앞수에서 뒷수를 뺀 값과 같아야 함
2. 뺀 값들의 최대공약수를 원래 리스트의 숫자에 더해줌
초기 코드 (2번을 실행하는게 어려움)
import sys
n = int(sys.stdin.readline())
hey = [map(int(sys.stdin.readline())) for _ in range(n)]
what = []
for i in len(hey):
a = hey[i+1] - hey[i]
what.append(a)
def gdc(a,b):
while b:
a,b = b, a%b
return a
수정
import sys
import math
def f_gcd(a,b):
while b > 0:
a,b = b,a % b
return a
n = int(input())
cnt = 0
arr = sorted([int(sys.stdin.readline()) for _ in range(n)])
sub = []
# 1)차이 구하기
for i in range(len(arr) -1):
sub.append(arr[i+1] - arr[i])
#2) 최대공약수 구하기
gcd = sub[0]
for i in range(1, len(sub)):
gcd = f_gcd(gcd, sub[i])
for j in sub:
cnt += j // gcd -1
print(cnt)개수 = 간격 // 최대공약수 - 1
import math 작동 방법 - for 최대공약수 구하기
import math
print(math.gcd(*sub))
[백준/Python] 2485. 가로수
동일한 간격으로 나무를 심어줘야 해서 그 도로(배열) 앞의 서로 인접한 값들의 차이를 구하고 그 차이로 나온 값들에서 공통된 가장 큰 약수 즉 최대공약수의 값으로 나무를 심어주면된다1) 입
velog.io
4134번 다음 소수
import sys
n = int(sys.stdin.readline())
sosu = []
for _ in range(n):
s = int(sys.stdin.readline())
for i in range(s, s+10):
if i%2 != 0 and i%3 !=0 :
sosu.append(s)
print(min(sosu))
예제 입력 1 복사
3
6
20
100
예제 출력 1 복사
7
23
101
예제에 입련된건 다 나오는데, 아마 범주 (for i in range(s, s+10)) 때문에 그런것 같음
임의로 설정한건데" 정수 n(0 ≤ n ≤ 4*109)가 주어졌을 때, "
+ 2와 3으로 나누어떨어지지 않는 것만으로는 소수임을 판단할 수 없음 (25)
import sys
def is_prime(num):
if num < 2:
return False
for i in range(2, int(num**0.5) + 1):
if num % i == 0:
return False
return True
n = int(sys.stdin.readline())
sosu = []
for _ in range(n):
s = int(sys.stdin.readline())
while True:
if is_prime(s):
sosu.append(s)
break
s += 1
print(min(sosu))제곱근까지만 활용하는 이유
- range(2, int(num**0.5) + 1):
- 2부터 num의 제곱근까지의 정수를 생성합니다.
- num**0.5는 num의 제곱근을 계산합니다.
- int()는 결과를 정수로 변환합니다.
- + 1은 range 함수가 끝 값을 포함하지 않기 때문에 추가합니다.
- 왜 제곱근까지만 확인하나요?
- 만약 num이 소수가 아니라면, num = a * b 형태로 표현할 수 있습니다.
- a와 b 중 적어도 하나는 반드시 √num 이하입니다.
- 따라서 √num까지만 확인해도 소수 여부를 판단할 수 있습니다.
- 효율성:
- 이 방법은 시간 복잡도를 O(√N)으로 줄여줍니다.
- 큰 수에 대해 매우 효율적입니다.
1929번 소수 구하기
초기 코드
import sys
def is_prime(num):
if num < 2 :
return False
for i in range (2, int(num**0.5)+1):
if num%i == 0:
return False
return True
sosu = []
m,n = map(int,sys.stdin.readline().split())
for i in range(m, n+1):
if is_prime(i):
sosu.append(i)
sosu = sorted(sosu)
for n in sosu:
print(n)
기본적으로 올바르게 작동하지만, 개선할 부분이 있다고 함.
그런데 백준에서는 attribute error 남
넓은 범위의 소수 계산을 하기 위해 가장 효율적인 방법 : 에라토스테네스의 채
에라토스테네스의 체
Sieve of Eratosthenes 고대 그리스의 수학자 에라토스테네스 가 만들어 낸 소수 를 찾는 방법.
namu.wiki
에라토스테네스의 채 구현 코드
def era(m,n):
primes = [True] * (n+1)
primes[0]=primes[1] = False
for i in range(2, int(n**5)+1):
if primes[i]:
for j in range(i+i, n+1, i): #어떤수의 배수가 되는 모든 수들)
primes[j] = False
return (num for num in range(max(2,m), n+1) if primes[num])1. 0부터 n까지 모든 수 소수로 가정하고 일단 true 로 초기화
2. 0 과 1은 소수가 아니므로 false
3. 2부터 n의 제곱근까지 반복
4. i 가 소수이면 i의 제곱부터 n까지의 i의 배수들을 모두 false 로 표시 (배수가 있다는 뜻은 소수가 아님)
5. m부터 n까지 숫자 중 primes[num]dl true 인것부터 반환
문제를 풀기위한 전체 코드
import sys
def era(m, n):
primes = [True] * (n + 1)
primes[0] = primes[1] = False
for i in range(2, int(n**0.5) + 1):
if primes[i]:
for j in range(i*i, n+1, i):
primes[j] = False
return (num for num in range(max(2, m), n+1) if primes[num])
m, n = map(int, sys.stdin.readline().split())
for prime in era(m, n):
print(prime)
4948번 베르트랑 공준
초기 코드
import sys
def era(m, n):
primes = [True] * (n + 1)
primes[0] = primes[1] = False
for i in range(2, int(n**0.5) + 1):
if primes[i]:
for j in range(i*i, n+1, i):
primes[j] = False
return (num for num in range(max(2, m), n+1) if primes[num])
sosu = [];
while True:
n = int(sys.stdin.readline().split())
if n== 0:
break
else :
for prime in era(n, 2*n+1):
sosu.append(prime)
print(len(sosu))type error 남
수정 코드
import sys
def era(m, n):
primes = [True] * (n + 1)
primes[0] = primes[1] = False
for i in range(2, int(n**0.5) + 1):
if primes[i]:
for j in range(i*i, n+1, i):
primes[j] = False
return [num for num in range(max(2, m), n+1) if primes[num]]
sosu = []
while True:
n = int(sys.stdin.readline().strip())
if n == 0:
break
else:
sosu.extend(era(n+1, 2*n))
print(len(sosu))
최적의 코드 - 범위가 주어졌으니 범위를 설정해주는게 좋음
import sys
def sieve_of_eratosthenes(n):
primes = [True] * (n + 1)
primes[0] = primes[1] = False
for i in range(2, int(n**0.5) + 1):
if primes[i]:
for j in range(i*i, n+1, i):
primes[j] = False
return primes
max_n = 123456 * 2
primes = sieve_of_eratosthenes(max_n)
while True:
n = int(sys.stdin.readline())
if n == 0:
break
count = sum(primes[n+1:2*n+1])
print(count)구성은 비슷한데 더 간단히 구현할 수 있었음
범위 설정도 잘못됨 - 조건이 n보다 크고, 2n보다 작거나 같은 소수의 개수 였기 때문에
'Algorithms > 백준알고리즘 연습' 카테고리의 다른 글
| 백준 알고리즘 약수, 소수와 배수 2 (2) (1) | 2024.12.22 |
|---|---|
| 백준 집합과 맵 (0) | 2024.12.11 |
| 백준 정렬(2) (2) | 2024.12.10 |
| 백준 부루트 포스 (복습 필요) (2) | 2024.12.09 |
| 백준 시간복잡도 (0) | 2024.12.07 |