반응형
반응형
문제
골드바흐의 추측 - '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])
반응형
'Algorithm' 카테고리의 다른 글
[파이썬] 재귀함수를 통한 팩토리얼의 구현 (17) | 2022.08.24 |
---|---|
[Python] 소수 판별/소수로 구성된 배열 생성 알고리즘 (24) | 2022.08.14 |
[Python] 백준 9020번 '골드바흐의 추측' 알고리즘 -2 (0) | 2022.08.06 |
[Python] 백준 1024번 '수열의 합' 알고리즘 (0) | 2022.08.01 |
스도쿠 풀이 알고리즘 (Back tracking method x, 초보자도 쉽게 따라할 수 있는 풀이) (2) | 2022.07.29 |
댓글