[백준/Python] 11653,1929,9020_소인수분해/소수시리즈

머리 아프다 ㅠㅠㅠ 코딩테스트 만든사람 만수무강하시구요 ^^ 얇은 슬리퍼 신고 가다가 우연히 버려진 레고 밟으셔서 3초정도만 아파주세요...

 

일단 소수/소인수 분해 문제는 정말 기본일 정도로 간단한 개념들이다. 소수는 1과 자기자신으로만 나눠지는 수, 소인수분해는 숫자들을 소수의 집합의 곱으로 나타내는것.

 

저 문제들을 풀면서 가장 머리가 아팠던 부분은 시간! 이 놈의 시간! 시간초과가 정말 괴로웠다.

그래도 시간초과가 되니까 오랜만에 time complexity 도 찾아보고 하는거징 ㅎ 아니면 게으른 내가 언제 찾아보겠나.

 

시간 초과가 되는 부분이 뭘까 고민을 많이했다. 비교 operator를 사용하는 부분에서 저런 일이 일어나는 걸까해서 찾아보니 그것보다는 반복문을 덜 돌리는게 시간 단축에 중요한 요소 같았다.

 

 

 

 

 

11653

소인수 분해하는 문제이다. 그냥 2부터 나누면 된다. 이렇게 하면 소수들로만 자연스럽게 나눠진다. //를 처음 사용해 보았다. 파이썬은 type상관없이 정직하게 소숫점까지 나누기 때문에 정수 나누기를 실행하여도 소수점으로 나오더라.

 

//를 사용하던지 type casting을 해주던지 해서 장치를 해 주어야 했다.

num = int(input())
quote= []
i = 1

while num != 1 :
    
    i += 1
    if num % i == 0 :
        quote.append(i)
        num = num // i
        i=1

for val in quote :
    print(val)

 

 

 

 

 

 

 

1929

아니 계속 시간 초과가 나길래 진짜 뭔가 했다 ㅋㅋㅋ 근데 에라토스테네스의 체로 푸는 문제였다.. 

 

에라토스테네스의 체는 모든 수를 소수라고 가정하고 소수인 수를 만나면 소수의 배수들을 모두 소수가 아니라고 표시하며 하나씩 없애가는 로직이다. 여기서 이해하기 힘든 부분이 한가지 있었다.

 

어떤 숫자의 소수를 체크하기 위해서는 제곱근 까지만 체크하면 된다.

그러니까 65가 소수인지 아닌지 알고싶으면 루트 65까지만 검사하면 된다는 뜻이다. 루트 65면 8.xxx이니까 8까지만 검사를 하면 된다는 뜻이다.

 

생각을 해보면 제곱근이라는 것 자체가 어떤것이 나눠진다는 반증이니까 제곱근 까지 답이 나오지 않는다면 그 수는 소수인것이 자명하다. 머리가 이해하는것을 거부하는건지 모르겠다 ㅎㅎ

 

start = 1
end = 10000

asternous = [True] * (end+1)
result = []

for j in range(2,int(end**0.5)+1) :
    if asternous[j] :
        for i in range(2*j,end + 1,j):
            asternous[i] = False

여기서 핵심은 제곱근 까지 진행하는 것과 프라임이이면 뒤에 배수들을 모두 프라임이 아니라고 표시하는것!

이렇게 하면 비교할것도 없이 그냥 착착 처리가 된다. 싱기방기 ~.~

 

 

 

 

 

9020

골드바흐씨에게는 화내지 않기로 했다 ^^ 

골드바흐의 추측이란 짝수는 두 개의 소수의 합으로 나타낼 수 있다는 가정이다.

아래 원칙을 세웠다.

 

1.시간 단축을 위해 만까지 프라임 여부 판단한 리스트 만들기
2.2로 나눠서 왼쪽, 오른쪽 친구들 설정
3.왼쪽은 빼가면서 오른쪽은 더해가면서 둘다 프라임이 될때까지 설정

 

start = 1
end = 10000

asternous = [True] * (end+1)
result = []

for j in range(2,int(end**0.5)+1) :
    if asternous[j] :
        for i in range(2*j,end + 1,j):
            asternous[i] = False

case_num = int(input())

for i in range(case_num) :
    input_n = int(input())
    
    if input_n < 4 or input_n > 10000 :
        continue
    
    left = int(input_n / 2)
    right = int(input_n / 2)
    
    while True :
        
        if asternous[left] and asternous[right] :
            print(left,right)
            break
        
        left -= 1
        right += 1

 

 

 

 

 

 

문제들이 전반적으로 연결되어 있어 스타트 문제를 잘 이해했다면 문제없이 이어서 풀 수 있는 문제들인것같다. 물론 나는 아니였다. ㅎㅎ 

 

어디가서 컴퓨터 공학과 학생이라고 말하기 부끄럽다ㅠㅠ

더 노력해야지 다시 한 번 다짐한다.

 

이래놓고 오늘 술마시러 가는건 안 비밀 ^^