알고리즘 3일차

 

오늘은 토요일 알고리즘 책을 절반정도, 검색 알고리즘까지 읽고

오늘까지 하노이탑까지 문제를 풀려고 한다.

 

이제 백준 9020번 골드바흐의 추측을 풀었는데 내 코드를 기록해두려고 일기장을 켰다.

 

문제를 보고 뭔가 풀 수 있을 것 같아서 힌트를 찾지 않고 어찌어찌 풀었다. ㅎㅎ

'맞았습니다!'라는 문구는 봤지만 다른 사람들 풀이 시간을 보니 나는 시간이 너무 오래 걸렸고,,,거의 15배,,,

반복을 최대한 줄였지만 뭔가 더 줄일 수 있을 것 같아 힌트를 찾아봤다 ㅎ.ㅎ

 

이게 웬걸 너무 간단한 방법이 있었고

시간이 정말 1/10로 줄었다 ㅋㅋ

힌트를 보고 풀었던 코드가 깃허브에 갱신되어서

꾸역꾸역 풀었던 내 허접한 코드가 날아가지 않게 여기 올려두려고 한다.

 

import math

def is_prime(n): # 2말고는 홀수만 삽입
    if n == 1: return False
    if n == 2: return True
    if n == 3: return True
    for i in range(3, int(math.sqrt(n)) + 1, 2):
        if n % i == 0:
            return False
    return True

count = int(input())

for i in range(count):
    num = int(input())
    prime = 2
    prime_set = []
    
    while True:
        if prime > (num // 2):
            break
        
        if is_prime(prime):
            if is_prime(num - prime):
                prime_set.append([prime, num - prime])
        if prime == 2:
            prime += 1
        else:
            prime += 2
    
    sub_min = prime_set[0][1] - prime_set[0][0] # 두 소수의 차이값
    min_index = 0
    for i in range(len(prime_set)):
        sub_set = abs(prime_set[i][0] - prime_set[i][1])
        if sub_min > sub_set:
            sub_min = sub_set
            min_index = i
    
    print(f"{prime_set[min_index][0]} {prime_set[min_index][1]}")

 

길다 길어,,,

 

https://blognavercomcheetah254.tistory.com/48

[백준 9020번] 골드바흐의 추측(파이썬)

이 분 블로그를 보고 힌트를 얻었다 ㅎㅎ