15단계 문제들 1탄
인트로
5문제를 한번에 적을 것이기 때문에 분량 및 문제 풀이 부분이 적을 수 있는 점 양해 부탁 ..
에라토스테네스의 체
소수를 판별하는 주요 알고리즘이다. (매우 자주 사용됨)
2는 소수임으로 2를 적고, 2의 배수 제거
3는 소수임으로 3을 적고, 3의 배수 제거
5는 소수임으로 5을 적고, 5의 배수 제거
...
이 과정 반복하면 소수 인 것만 남는다는 알고리즘
def prime_list(n):
# 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주)
sieve = [True] * n
# n의 최대 약수가 sqrt(n) 이하이므로 sqrt(n)까지 검사
m = int(n ** 0.5)
for i in range(2, m + 1):
if sieve[i] == True: # i가 소수인 경우
for j in range(i+i, n, i): # i이후 i의 배수들을 False 판정
sieve[j] = False
# 소수 목록 산출
return [i for i in range(2, n) if sieve[i] == True]출처 : 위키백과
1934번 - 최소공배수
말 그대로 입력 받은 A,B의 최소공배수를 출력하면 된다.
python에는 math에 lcm (최소공배수) / gcd (최대공약수) 함수가 있다.
이를 참고하면 된다.
코드
import math
T = int(input())
for i in range(T):
A, B = map(int,input().split())
answer = math.lcm(A,B)
print(answer)13241번 - 최소공배수
이것도 그냥 최소공배수 구하면 된다.
코드
import math
A, B = map(int,input().split())
answer = math.lcm(A,B)
print(answer)1735번 - 분수 합
1/3 + 2/4 -> 10/12 = 5/6 인 것처럼 입력 받는 분수의 합을
기약분수 (=더이상 나눠지지 않도록) 형태로 출력시키는 것이 목표이다.
분수 계산하듯이 두 분모는 최소공배수로 해주고, 이를 나눈 값만큼 분자에 곱해준 다음
분모와 분자가 최대공약수를 구해 그만큼 나누어 기약분수 형태로 구해주면 된다.
코드
import math
A, B = map(int,input().split()) # A/B
C, D = map(int,input().split()) # C/D
# A/B + C/D = ((A*D)+(B*C))/(B*D) 을 구한 뒤에 분자, 분모 최대 공약수로 나눠주면 됨.
lower = math.lcm(B,D) #더한 값의 분모
higher = int(A*(lower/B)+C*(lower/D)) #더한 값의 분자
div = math.gcd(lower,higher) #합 분수의 분모,분자의 최대공약수
print(higher//div,lower//div) #기약분수로 출력2485번 - 가로수
가로수의 현재 심어져있는 위치들이 나온다.
예를 들어, (1,3,7,13) 이라면 (5,9,11) 위치에 가로수를 더 심어서 간격을 같게 하면 된다.
이 문제는 결국 현재 심어져 있는 가로수들의 간격들 중에서 최대공약수를 구해야 한다.
예시의 경우 2,4,6이기 때문에 최대 공약수는 2가 된다.
따라서 2만큼의 간격으로 나머지 가로수들이 5,9,11 에 심어져야 한다.
이 아이디어로 구현을 해보았다.
코드
import math
N = int(input())
temp = [] #입력 저장 리스트
dis = [] #입력들의 거리를 저장할 리스트
for i in range(N):
temp.append(int(input()))
for i in range(1,N):
dis.append(temp[i]-temp[i-1]) #가로수끼리의 거리를 dis 에 저장
gcd = math.gcd(*dis) #리스트들 전체의 최대공약수를 저장
totalneed = int((max(temp)-min(temp)) / gcd)+1 #전체 거리에서 필요한 만큼 출력
print(totalneed - len(temp))밑에서 두 번째 코드에 +1을 해준 이유는 다음과 같다.
출처 : 유퀴즈 유튜브
딱 이런 상황인데 ..ㅋㅋㅋㅋ
간격이 6지점이라면 나무는 1개 더 필요하니까 ^^.. 어른들은 이해하겠죠 ?
그리고 !!!!
여러 개의 최소 공배수나 최대 공약수를 한번에 출력하기 위해 리스트 언패킹을 이용했다.
출처 : 코딩도장
이를 이용하면 gcd (*리스트이름) 하면 리스트 전체의 최대공약수를 구할 수 있다.
4134번 - 다음 소수
정수가 주어지는데, 해당 정수보다 같거나 큰 소수를 출력하면 된다.
예를 들어, 6의 경우는 7을 출력하면 되고, 3의 경우는 3을 출력하면 된다.
코드
def isprime(x):
if x == 0 or x == 1:
return False
for i in range(2, int(x**0.5)+1):
if x % i == 0:
return False
return True
T = int(input())
for _ in range(T):
n = int(input())
while True:
if n == 1:
n += 1
if isprime(n):
print(n)
break
n += 1에라토스테네스의 체를 이용한 방법이다.
isPrime 함수에서 입력 받는 x의 제곱근의 범위까지 돌면서 해당 값까지 나누어떨어지는 값이 없다면
소수라고 판명을 해준다.
또한, n == 1일 때는 2가 되야 함으로 +1 의 예외처리를 해주고, 그 외의 사항들에는 입력 받은 값을
isPrime 함수로 넘긴 다음 함수가 참이 된다면 현재의 값을 출력한다.
참이 되지 않으면 +1씩 더해주면서 계속 확인한다.
후기
세상에 이런 문제들만 있다면 나는 천재였을테야
