[Python/파이썬] [🥈2] 백준 알고리즘 9020 - 골드바흐의 추측

📖[Python/파이썬][🥈2] 백준 알고리즘 9020 - 골드바흐의 추측

📜문제

---

📕풀이방향

N이 2의 배수인데다, N의 범위도 만만해서 2~n까지 2의배수만 모두 소수를 구해 저장해놓고,
abs(절댓값)함수로 N의 소수들을 비교하면서 출력할 생각을 하면 큰 코 다친다...🤦🏻‍♀️

내 포스팅 : [Python] 백준 알고리즘 4948 - 베르트랑 공준
이전 포스팅에서 위 문제를 해결한 경험으로부터 소수를 리스트에 저장해두는 방법을 떠올려,
상기 풀이처럼 해결하려고 했으나 또 다시 시간초과에 직면했다😭

👉🏻수학적으로 접근하자
n을 입력받되 a,b에 n//2를 각각 저장하여 prime(a)와 prime(b)가 둘 다 소수이면 출력,
소수가 아니면 a--, b++하며 다시 비교하는 방식으로 풀어보자
a,b 초기값을 n//2으로 지정한 이유 = n이 10인 경우 5,5가 제일 차이가 작으니까

---

📝알고리즘 구현순서

1. 소수를 구하는 prime()함수를 만들자
2. t만큼 n을 입력받으며 a,b에 n//2값을 저장하여 prime(a)와 prime(b)가 True이면 출력하자
   (하나라도 False이면 a++, b--)

---

💻결과코드

import sys
input = sys.stdin.readline

t = int(input().rstrip())

def prime(n):
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True

for _ in range(t):
    n = int(input().rstrip())
    a,b = n//2, n//2
    while a > 0:
        if prime(a) and prime(b): #둘 다 True(소수)인 경우
            print(a, b)
            break
        else:
            a -= 1
            b += 1

❓이 코드가 효율적인 이유

👉🏻 모든케이스의 prime()을 저장하게 만드는게 문제의 함정인데, 
   위 코드는 a,b만 prime()을 호출하여 둘 다 True를 반환할 때만 출력한다.
   (모든케이스를 prime()하면 n번 / a,b만 prime()하면 n/2번만 호출하게됨!)

---

✏️1. prim() 함수 만들기 (소수이면 True, 아니면 Flase 반환)

import sys
input = sys.stdin.readline

t = int(input().rstrip())

def prime(n):
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True

---

✏️2. n//2를 a,b에 저장하여 prime(a) and prime(b) → true이면 출력

for _ in range(t):
    n = int(input().rstrip())
    a,b = n//2, n//2
    while a > 0:  #a를 a--해가면 결국 0에 도달할 테니까 1이 될 때까지만 실행
        if prime(a) and prime(b): #a,b 다 True이면 출력
            print(a, b)
            break
        else: #하나라도 False이면 a--, b++후 다시 검사
            a -= 1
            b += 1

---

📚초기 알고리즘 오류와 정리

※초기 알고리즘

✍🏻 N의 소수를 다 구하여 절댓값이 최소값이면 출력하기

import sys
input = sys.stdin.readline

t = int(input().rstrip())

def prime(n):
    res = []
    res_prime = ''
    for num in range(n):
        err = 0
        for i in range(2,int(num**0.5)+1):
            if num%i == 0:
                err += 1
        if err == 0:
            res.append(num)
    cnt = max(res)-min(res)
    for a in res:
        for b in res:
            if a+b == n:
                if abs(a-b) < cnt:
                    cnt = abs(a-b)
                    res_prime = str(a)+' '+str(b)
                else:
                    pass
    return res_prime

for _ in range(t):
    n = int(input().rstrip())
    print(prime(n))

❓내 알고리즘이 틀린 이유

틀리지않았다. 정답이다.
그러나 n이 입력될 때마다 모든 소수를 구하여 list(res)에 저장하고,
res를 다시 절댓값을 비교하면서 prime()안에서 불필요한 for/if문 동작이 많기 때문에
시간초과를 발생시켰다

---

1. 알고리즘 설계 과정에서 O(N)를 생각하는 것은 이제 당연하다
   '전체 알고리즘이 어떻게 동작할지 / 동작하면서 불필요한 계산은 없는지'
   확인하는 과정이 매우 중요하다

   어떤 경우는 전체 과정을 다 계산하여 저장하고
   그것을 뽑아 쓰는 것이 효율적인 알고리즘이 되겠지만,
   
   또 어떤 경우는 전체 과정을 다 계산하는 것보다
   필요한 경우만 계산하며 결과를 도출해내는 것이 효율적인 알고리즘이 될 수 있다....