[Python] 백준 9020번 '골드바흐의 추측' 알고리즘 -1

반응형

문제

 

골드바흐의 추측  -  '2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다'

4 이상의 짝수를 입력받고, 그 짝수를 두 소수의 합으로 출력하는 알고리즘을 구현하시오. 만약 골드바흐 파티션(하나의 짝수를 두 소수의 합으로 나타내는 표현)이 여러개인 경우, 두 소수의 차이가 가장 작은 파티션을 출력하시오

 

초기 idea

 

문제에서 4이상 10000 이하의 짝수를 입력받으므로, 10000 이하의 소수로 구성된 리스트를 생성한다. 이를 위해 소수인지 아닌지를 판별할 수 있는 함수를 선언한다.

 

앞서 생성한 소수 리스트내에서 이중 반복문을 활용하여 입력받은 짝수에 대한 파티션을 반환하는 함수를 선언한다. 

만약 파티션이 여러개인 경우, 문제의 조건에 따라 두 소수의 차이가 가장 작은 파티션을 반환한다.

 

한계 및 개선 방향

 

코드는 정상적으로 작동하지만, 코드 실행시간이 너무 긴 것이 문제였다. 백준 사이트 내에서도 '시간 초과'로 틀렸다는 판정을 받았다.

 

먼저 소수 리스트내의 모든 원소 값을 확인해야 하는 반복문의 비효율성에 대해 고민해보고, 자료구조의 변형 등, 추가적인 최적화 방법을 공부해야겠다.

# 소수의 리스트를 만들고, 하나의 짝수가 주어졌을 때, 그 짝수를 두 소수의 합으로 표현할 수 있을
# 때까지 반복문을 반복 및 출력

# 소수의 리스트를 형성하기 위해서 주어진 수가 소수인지 아닌지 판별할 수 있는 함수 생성

def prime(x):
    tf = 0
    for i in range(2, x):
        if (x % i == 0):
            tf = 1
    return tf

# 2보다 크고 10000보다 작은 짝수를 입력받으므로, 10000이하의 소수로 리스트를 구성

prime_arr = []
for i in range(2, 10001):
    if prime(i) == 0:
        prime_arr.append(i)

# 앞서 생성한 소수로 구성된 리스트, prime_arr에서 만들 수 있는 합의 조합으로 구성된 리스트 생성

def Goldbach(x):
    solution_arr = []
    final_solution_arr = []
    for i in range(len(prime_arr)):
        for j in range(len(prime_arr)):
            if (prime_arr[i] + prime_arr[j]) == x:
                    solution_arr.append([prime_arr[i], prime_arr[j]])
#                     print('solution_arr', solution_arr)
    if len(solution_arr) > 1:
        min_arr = []
        for k in range(len(solution_arr)):
            min_arr.append(abs(solution_arr[k][0] - solution_arr[k][1]))
            min_differ = min(min_arr)
            min_differ_index = min_arr.index(min_differ)
                        
        final_solution_arr.append(solution_arr[min_differ_index])
#         print('min_arr', min_arr)
#         print('min_differ', min_differ)
#         print('min_index', min_differ_index)
                
    else:
        final_solution_arr = solution_arr

    return final_solution_arr

# 입력부

T = int(input())

test_arr = []
for i in range(T):
    test_num = int(input())
    test_arr.append(test_num)
    
# 출력부

for i in range(T):
    solution = Goldbach(test_arr[i])
    solution[0] = sorted(solution[0])
    print(solution[0][0], solution[0][1])