백준 [단계별로 풀어보기]: (15단계) "약수, 배수와 소수2", python

백준 [단계별로 풀어보기]: (15단계) "약수, 배수와 소수2", python

 

1. 문제번호 및 정답비율

15단계 약수, 배수와 소수2 : 문제번호 및 정답 비율

2. 문제별 필요 지식 및 풀이 포인트

#1. 1934 최소공배수,  # 2. 13241 최소공배수

1. 최대공약수gcd를 "반복문while"형태로 구현한다.

  why? python3기준 최대재귀깊이는 1000이다. 그래서, 재귀함수 사용 시, RecursionError가 발생한다.

  why? "재귀함수깊이 늘리기"를 해도 안 되기 때문이다. <= import sys; sys.setrecursionlimit(10**6)

2. 최소공배수의 정의lcm=a*b/gcd를 활용한다.

3. 1,2가 싫다면 import math 라이브러리를 활용한다.

#3. 1735 분수 합

분자/분모 약분에 대한 조건을 넣어주어야 한다.

# 4. 2485 가로수 / 실패, 후에 다시 풀기

#5. 4134 다음 소수 / 실패, 후에 다시 풀기

 

# 6. 1929 소수 구하기

정수론에서 소수란? "임의의 양의 정수 m이 루트m 보다 작거나 같은 약수를 가지지 않으면 m은 소수이다."

(참고: https://8iggy.tistory.com/21)

math라이브러리에서
- math.sqrt(x)는 x의제곱근(x**0.5)
- math.pow(x,y)는 x의y승(x**y)을 반환
- SQL에서 select sqrt(20/pi()); pi()는 원주율을 의미하며, 반지름을 구하는 공식이다.
(참고: https://docs.aws.amazon.com/ko_kr/clean-rooms/latest/sql-reference/r_SQRT.html)

 

 

#7. 4948 베르트랑 공준 / 실패, 후에 다시 풀기

Bertrand's postulate은 정수론에서 소수의 분포에 관한 정리로, 임의의 정수 n>=2에 대해 n<p<2n인 소수p가 항상 존재한다.

# 8. 17103 골드바흐 파티션 / 실패, 후에 다시풀기

Goldbach's conjecture은 2보다 큰 모든 짝수는 두 개의 소수(Prime number)의 합으로 표시할 수 있다.
ex) 4=2+2 / 6=3+3 / 8=3+5 / 10=3+7=5+5 / 12=5+7 / ...
중복조합으로 풀었는데, 메모리초과로 다른 방법으로 풀어야 한다. (from itertools import combinations_with_replacement #중복조합)

# 9. 13909 창문 닫기

우선 스크립트에 무조건 써보면서 규칙성을 찾으려고 노력했다.

'''                                              n
1,1 1 = 1 (s)
2,10 1      ~    
3,100 1 = 3 (e)                         2
4,1001 2 = 1+3 (s)
5,10010 2
6,100100 2        ~
7,1001000 2
8,10010000 2 = 3+5 (e)           3
9,100100001 3 = 1+3+5 (s)
10,1001000010 3            ~
...
15,100100001000000 3 = 3+5+7 (e) 4
16,1001000010000001 4 = 1+3+5+7 (s)
...'''

1st. 입력값n이 속한 범위를 찾아내기(시작start과 끝end 둘 다 알아내야 함)

    -> 끝end점 기준으로만 생각해서 시작start점에 대한 값이 출력이 잘못되서 나옴 (시간소요: 90%이상)
2nd. n에 대한 열려있는 창문수m의 상관관계를 찾아내기

    -> 입력값n과 m의 상관관계를 찾지 못함 (시간소요: 10%)

3. 문제별 풀이 코드

#1. 1934 최소공배수
'''재귀함수로 구현, 포인트는 lcm=a*b/gcd
import sys
sys.setrecursionlimit(10**6) <-1.RecursionError해결책 : 재귀함수깊이늘리기

def gcd(a,b): #Greatest Common Divisor
    if b != 0 and a % b == 0: # b!=0 안할 시 ZeroDivisionError 발생
        return b
    else:
        return gcd(b, a&b)
def gcd(a,b): #Greatest Common Divisor <-2.RecursionError해결책 : 재귀대신 반복문사용
    while b>0:
        a,b = b, a%b
    return a
        
for i in range(int(input())): #RecursionError: python3기준 최대 재귀 깊이 1000
    a, b = map(int, input().split())
    def lcm(a,b): #Least Common Multiple
        return a*b/gcd(a,b)
    print(int(lcm(a,b)))'''

def gcd(a,b): #RecursionError해결책 : 재귀대신 반복문사용
    while b>0:
        a,b = b, a%b
    return a
for i in range(int(input())):
    a, b = map(int, input().split())
    def lcm(a,b):
        return a*b/gcd(a,b)
    print(int(lcm(a,b)))
    
import math #math라이브러리: https://docs.python.org/ko/3/library/math.html
for i in range(int(input())):
    a, b = map(int, input().split())
    print(math.lcm(a,b))
    

# 2. 13241 최소공배수
import math
a,b = map(int, input().split())
print(math.lcm(a,b))

''' lcm=a*b/gcd
def gcd(a,b): #10 6
    while b>0:
        a,b = b,a%b #6 4, 4 2, 2 0 
    return a
def lcm(a,b):
    return a*b/gcd(a,b)
print(int(lcm(a,b)))'''


#3. 1735 분수 합
import math
a,a1 = map(int, input().split())
b,b1 = map(int, input().split())
#print(a*b1+b*a1, a1*b1) #자/모 약분 여부를 안 넣어줘서 틀림
numerator = a*b1+b*a1 #자
denominator = a1*b1 #모
gcd = math.gcd(numerator, denominator)
#print(gcd)
if math.gcd(numerator, denominator) > 1:
    print(int(numerator/gcd), int(denominator/gcd))
else:
    print(int(numerator), int(denominator))
    

# 4. 2485 가로수
'''모든 가로수가 같은 간격이 되도록 새로 심어야 하는 가로수의 최소 갯수'''
n = int(input()) #현재 심어져있는 나무 그루 4
t = sorted(set(int(input()) for i in range(n)) #1 3 7 13
print(t) #5 9 11 => 3


# 5. 4134 다음 소수
'''소수함수정의'''
def prime(a): #2부터(a-1)까지의 수로 나누기
    for i in range(2,a):
        if a%i == 0:
            return False
    return True
'''아래 코드는 시간초과'''
n = int(input())
for _ in range(n):
    n = int(input())
    while n <= 4*10**9: #소수일때,
        if prime(n): #소수일때,
            print(n)
            break #break안하면 loop걸림
        else:
            n += 1


# 6. 1929 소수 구하기
'''정수론적 관점에서
소수란? 임의의 양의 정수 m이 루트m 보다 작거나 같은 약수를 가지지 않으면 m은 소수.
참고: https://8iggy.tistory.com/21

math라이브러리에서
- math.sqrt(x)는 x의제곱근(x**0.5)
- math.pow(x,y)는 x의y승(x**y)을 반환
- SQL에서 select sqrt(20/pi()); pi()는 원주율을 의미하며, 반지름을 구하는 공식이다.
참고: https://docs.aws.amazon.com/ko_kr/clean-rooms/latest/sql-reference/r_SQRT.html
'''
import math
def prime(x):
    if x<2: return False #1 is not prime: 예외처리 해주지 않으면 틀림
    for i in range(2,int(math.sqrt(x))+1): #2에서 n-1까지의 수로 나눠지지 않았을 때
        if x%i == 0:
            return False
    return True

m, n = map(int, input().split())
for i in range(m, n+1):
    if prime(i):
        print(i)
    else:
        continue


#7. 4948 베르트랑 공준
'''공준(postulate): 가정,조건
Bertrand's postulate: (정수론에서 소수의 분포에 관한 정리로,)
임의의 정수 n>=2에 대해 n<p<2n인 소수p가 항상 존재한다.
'''
'''으아아!! 시간초과!! while문 안을 if n <= 123456:로 감싸줘도 시간초과 발생'''
import math
def prime(x):
    if x<2: return False
    for i in range(2, int(math.sqrt(x))+1):
        if x%i == 0:
            return False
    return True
    
while True:
    n = int(input()) #n입력 먼저 받고, <n=0이면 break> 예외처리를 추가
    if n == 0:
        break
    cnt = 0 #소수의 개수 담을 객체 0으로 초기화
    for i in range(n+1, 2*n+1):
        if prime(i):
            cnt += 1
    print(cnt)


# 8. 17103 골드바흐 파티션
'''Goldbach's conjecture
2보다 큰 모든 짝수는 두 개의 소수(Prime number)의 합으로 표시할 수 있다.
ex)4=2+2 / 6=3+3 / 8=3+5 / 10=3+7=5+5 / 12=5+7 / ...
'''
'''중복조합 사용 시, 메모리초과'''
from itertools import combinations_with_replacement #중복조합
import math
def prime(x):
    if x<2: return False
    for i in range(2, int(math.sqrt(x))+1):
        if x%i == 0:
            return False
    return True

m = int(input())
for _ in range(m):
    n = int(input()) #n은 짝수
    arr = []
    for i in range(2,n+1):
        if prime(i):
            arr.append(i)
    #print(arr)
    result = 0
    for a,b in list(combinations_with_replacement(arr,2)):
        if a+b == n:
            result += 1
    print(result)


# 9. 13909 창문 닫기
'''첫번째 풀이 : 날 것 그대로의 풀이'''
'''                              n
1,1 1 = 1 (s)
2,10 1      ~    
3,100 1 = 3 (e)                  2
4,1001 2 = 1+3 (s)
5,10010 2
6,100100 2        ~
7,1001000 2
8,10010000 2 = 3+5 (e)           3
9,100100001 3 = 1+3+5 (s)
10,1001000010 3            ~
...
15,100100001000000 3 = 3+5+7 (e) 4
16,1001000010000001 4 = 1+3+5+7 (s)
...'''
#an = 1+3+5+7+9 = 2n-1 (n>=2) : 
#Sn = n^2 -1 (n>=2) : Sn번째 숫자까지, 열려있는 창문 수는 n-1
import math
n = int(input())
#for i in range(2, int(math.sqrt(n+1))+1): 여기서 계속 끝end점만 제대로 출력되고, 시작start점에 대한 정보를 찾기 어려웠음
#    print(int(math.sqrt(n+1))-1)

m = int(math.sqrt(n))
if math.pow(m,2) <= n <= math.pow(m+1,2)-1: # (s)~(e)
    print(m)
    
'''두 번째 풀이 : 알아보기 쉽게 다시 정리했습니다.'''
#1st. 입력값n이 속한 범위를 찾아내기(시작start과 끝end 둘 다 알아내야 함)
#2nd. n에 대한 열려있는 창문수m의 상관관계를 찾아내기
import math
n=int(input())
m=int(math.sqrt(n)) #n과 m의 상관관계
if math.pow(m,2)<=n<=math.pow(m+1,2)-1: #n이 속한 범위
    print(m)    
'''
문제풀이 중 교착상태에 걸린 이유?
첫번째, 끝end점 기준으로만 생각해서 시작start점에 대한 값이 출력이 잘못되서 나옴 (시간소요:90%이상)
두번째, 입력값n과 m의 상관관계를 찾지 못함 (시간소요:10%)
'''
'''
다른사람의 풀이
1. n과 m의 상관관계만 구한다면, 범위는 필요없어진다.
2. 1을 결과로 갖는 창문은 어떤수m의 제곱수이므로, n제곱수의 제곱근m을 구해주면 된다.
'''