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

이번 포스팅은 앞선 백준 9020번, 골드바흐 파티션 출력 알고리즘의 개선방법에 대해 다뤄보겠습니다.

 

처음 코드와 한계 및 개선 방향은 아래의 링크에서 확인하실 수 있습니다.

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

 

처음 코드에서는 모든 예제 값들에 대해서 출력은 정상적으로 되지만, '실행 시간' 문제에 따른 백준에서의 '시간 초과'가 문제였습니다.

 

이를 해결하기 위해서 먼저 두 가지 방법을 시도해보았습니다.

 

1) 자료구조의 변형

 

  데이터(자료)를 사용하는 방법에 따라 효율적인 데이터 저장 방법(list, tuple, dictionary, 집합 등)을 사용하면, 실행 시간을 단축시킬 수 있음을 알게 되었습니다. 하지만 소수로 구성된 배열에서 반복문을 활용하여 파티션을 출력해야 하는 전체적인 알고리즘의 방향성의 이유로 기존의 데이터 저장방법 'list'를 유지했습니다. 

 

 

2) 코드의 입력부 수정

 

  다수의 입력을 받을 때, input()을 사용하는 것보다 sys 모듈의 sys.stdin.readline()을 사용하는 것이 실행 시간을 단축시킬 수 있음을 알게되었습니다. 수정 결과 실행시간이 약 10ms 단축되었지만, 문제 해결을 위해서는 부족했습니다.

 

 

 결국, 사소한 부분에서의 수정이 아니라, 코드의 전체적인 변화가 필요함을 깨닫고, 시간 초과의 원인이라고 생각되는 '반복문'의 효율성에 대해서 고민하기 시작했습니다.

 

 10000개의 소수로 구성된 배열에서 이중 반복문을 통해 입력받은 짝수에 대해 골드바흐 파티션을 출력하는 기존의 방법 대신에 입력값이 짝수라는 점을 활용하여 파티션을 구성하는 수가 소수인지 판별하는 알고리즘으로 수정함으로써, 문제를 해결할 수 있었습니다.

 

 문제의 조건에 의해 여러 파티션이 존재하는 경우, 두 수의 차가 가장 작은 파티션을 출력해야 했기 때문에, 기존의 방법에서는 입력받은 짝수에 대해서 골드바흐 파티션을 찾았다고 하더라도, 그 파티션이 문제에서 요구하는 정답이 아닐 수 있기 때문에 끝까지 반복문을 실행해야 했습니다. 또한,  그 다수의 파티션들에 대해서 두 소수의 차를 계산, 최솟값을 반환, 해당 인덱스 값의 파티션을 출력해야 했습니다.

 

 하지만, 수정된 방법에서는 파티션을 구성하는 두 수의 차가 작은 순서대로 진행되었기 때문에, 두 수가 소수임이 확인되면, 바로 그 파티션이 문제에서 요구하는 골드바흐 파티션임을 알 수 있었습니다.

 

알고리즘을 구현하는 데 있어서, 실행 시간이 문제인 경우, 기술적인 수정도 중요하겠지만, 여러 줄의 코드 속의 논리(핵심적인 문제 해결방법)의 효율성을 따져보는 것이 중요한 것 같습니다. 

 

# 소수로 구성된 리스트 prime_arr를 생성하기 위해서 특정 수(n)이하의 수가 소수인지 아닌지를
# 판별하는 함수 선언

def prime(n):
    
    sieve = [True] * n
    m = int(n**0.5)
    for i in range(2, m + 1):
        if sieve[i] == True:
            for j in range(i+i, n, i):
                sieve[j] = False
    
    return [i for i in range(2, n) if sieve[i] == True]

# 10000이하의 짝수를 입력받고, 우리는 소수의 규칙성에 대해 알지 못하므로, 누락을 피하기 위해
# 10000이하의 소수를 모두 prime_arr에 담음

prime_arr = prime(10000)

# test case의 개수 입력부

T = int(input())

# 짝수 입력 및 골드바흐 파티션 출력부

for i in range(T):
    test_num = int(input())
    div = int(test_num/2)
    for i in range(0, div):
        if ((div - i) in prime_arr) and ((div + i) in prime_arr):
            solution_arr = [div - i, div + i]
            break
    print(solution_arr[0], solution_arr[1])