[백준][문제 풀기] 알고리즘 기초 1/2 - 6588 골드바흐의 추측

이번 문제에서 물어보는 것은 세가지이다.
얼마나 불필요한 코드를 잘 제거하는지
에라토스테네스의 채를 알고 있고 구현 할 수 있는지
게다가 시간제한이 꽤나 까다롭다

---

거두절미하고 바로 코드로 들어가자

"""

백준 6588 골드바흐의 추측

"""

import sys

def is_prime (num) :
    if num < 2 : return False
    for i in range(2, num) :
        if num%i == 0 :
            return False
    return True

if __name__ == "__main__" :

    while True :
        # 데이터를 잘 받자!
        num = int(sys.stdin.readline().strip())
        if num == 0 : break

        primes_odd = []
        for i in range(num) :
            if is_prime(i) and i%2 == 1 : primes_odd.append(i)

        for v in primes_odd :
            is_find = False
            for vv in primes_odd :
                if v == vv : continue
                if v + vv == num : 
                    if v > vv : 
                        tmp = v
                        v = vv
                        vv = tmp
                    print(f"{num} = {v} + {vv}")
                    is_find = True
                    break
            if is_find : break
        if not is_find : print("Goldbach's conjecture is wrong")

실패 한 코드

• 일단 첫 시도는 의식이 흐르는대로 진행했다
• 타겟이 되는 숫자를 받음 -> 이하 소수들을 모음 -> 각각의 소수를 더했을 때 타겟 한 숫자인지 체크 -> 작은 수를 앞에 두고 print, break
• 역시나 예상대로 시간초과가 뜬다

"""

백준 6588 골드바흐의 추측

"""

import sys

def is_prime (num) :
    if num < 2 : return False
    for i in range(2, int(num**0.5)) :
        if num%i == 0 :
            return False
    return True

if __name__ == "__main__" :

    primes_odd = [False] * 10000

    for i in range(10000) :
        if is_prime(i) and i%2 == 1 : 
            primes_odd[i] = True

    while True :
        # 데이터를 잘 받자!
        num = int(sys.stdin.readline().strip())
        if num == 0 : break

        a = num//2
        b = num//2

        find = False
        for i in range(10000//2) :
            if a < 2 or b > 10000 : break
            if not primes_odd[a] :
                a -= 1
                continue
            if not primes_odd[b] :
                b += 1
                continue

            if a + b == num :
                print(f"{num} = {a} + {b}")
                find = True
                break

        if not find : print("Goldbach's conjecture is wrong")

역시 실패 한 코드

• 무수히 많은 시도들 중 또 다른 시도
• list에 append 하고 in으로 찾던 소수목록을 타겟 number 받기 전에 미리 만듦
• a와 b를 설정하고 중앙에서부터 바깥으로 찾아가도록 변경
• 소수를 찾는 과정에서 n이 아닌 n의 제곱근 사용
• 했지만 여전히 시간초과다

"""

백준 6588 골드바흐의 추측

"""

import sys

MAXVAL = 100002

def find_primes () :

    primes = [True] * MAXVAL
    primes[0] = False
    primes[1] = False

    for i in range(2, int(MAXVAL**0.5)+1) :
        for ii in range(i*2, MAXVAL, i) :
            primes[ii] = False
    return primes

if __name__ == "__main__" :

    primes = find_primes()

    while True :
        # 데이터를 잘 받자!
        num = int(sys.stdin.readline().strip())
        if num == 0 : break
        a = num - 3
        b = 3

        find = False
        while b <= a :

            if not primes[a] :
                a -= 1
                continue
            if not primes[b] :
                b += 1
                continue

            if a + b == num :
                print(f"{num} = {a} + {b}")
                find = True
                break
            else :
                a -= 1
                b += 1

        if not find : print("Goldbach's conjecture is wrong")

역시 실패 한 코드

• 이 코드 또한 시간초과가 뜬다.
• 이 경우 에라토스테네스의 채를 사용했는데도 마찬가지였다.

"""

백준 6588 골드바흐의 추측

"""

import sys

MAXVAL = 1000002

def find_primes () :

    primes = [True] * MAXVAL
    primes[0] = False
    primes[1] = False

    for i in range(2, int(MAXVAL**0.5)+1) :
        for ii in range(i*2, MAXVAL, i) :
            primes[ii] = False
    return primes

if __name__ == "__main__" :

    primes = find_primes()

    while True :
        # 데이터를 잘 받자!
        num = int(sys.stdin.readline().strip())
        if num == 0 : break
        a = 3
        b = num - 3

        find = False
        while a <= b :

            if not primes[a] or not primes[num-a] :
                a += 1
                continue
            # if not primes[b] :
            #     b -= 1
            #     continue
            b = num-a

            if a + b == num :
                print(f"{num} = {a} + {b}")
                find = True
                break
            else :
                a += 1
                b -= 1

        if not find : print("Goldbach's conjecture is wrong")

정답 코드

• 직전 코드와 다른 점은 b, a를 구할 때 a값이 소수인지를 구하고, b값을 n-a로하여 소수인지를 구한다는 점이다
• 둘 사이의 시간복잡도는 정확히 계산 하기는 어려울것
• a가 소수인지 판단 -> b가 소수인지 판단 -> a+b=n인지 판단
• a가 소수인지 판단 -> a+b=n을 갖는 b가 소수인지 판단
• 위 케이스와 비교 할 때 계산량이 분명히 적어진다는 장점이 있는 것 같다
• 대략 n과 2n 정도의 복잡도 차이일 것으로 판단된다
• 이정도까지 요구한다는 것은 이 문제가 (내기준)상당히 까다로운 문제인 것 같다