[Baekjoon] Baekjoon 1929 문제 풀이
알고리즘 공부를 오랜기간 손을 놓았고, 다시 기본기부터 해보자는 마음에 Baekjoon 에서 단계별 문제를 푸는 도중에 1929 문제를 만났습니다만 문제를 풀기 위한 알고리즘을 알지 못하면 풀 수 없는 문제였고, 문제를 풀기 위한 알고리즘을 공부한 후 문제를 풀었습니다. 스스로 공부도 하고 추후에 까먹었을 때를 대비해 포스트로 문제 푸는 과정을 기록하고자 포스트 작성을 하게 되었습니다.
1. 문제 소개
Baekjoon 사이트의 정책상 문제의 저작권은 문제를 만든 사람에게 있다고 합니다. 그래도 블로그에 문제와 관련해서 링크로 넣는 것은 상관 없다고 하여 문제 내용은 링크로 대체하겠습니다. 자세한 문제 내용은 링크를 통해 사이트를 방문하여 확인해 주시길 바랍니다.
2. 문제 풀이
풀이 내용
문제 내용을 보시고 오시면 알겠지만 문제는 소수를 구하는 문제입니다. 문제 내용이 간단한 것에 비해서는 굉장히 어렵다고 생각됩니다. 우선 제가 생각하는 이 문제를 풀기 위한 핵슴은 다음과 같습니다.
- 최악의 경우 1~1,000,000 의 수를 모두 소수인지 판별해야 해서 시간 초과를 고려 해야함
- 소수의 성질에 대해서 알아야 함
- 소수를 구하는 알고리즘에 대해서 알아야 함
저는 처음에 문제의 내용이 간단하고, 소수 구하는게 어려운 것인가? 하는 생각에 무턱대고 도전했다가 처참하게 깨졌고, 왜 문제의 정답 비율이 낮은지 알 수 있었습니다. 그리고 다시 한 번 제가 수학이 약하다는 것을 깨달았고, 소수라는 수가 굉장히 어려운 수라는 것을 알게 되었습니다.
그리고 저는 어렸을 때 주입식 교육으로 소수는 그냥 1이랑 자기 자신만을 약수로 가지는 수야 라는 것이 아니라 소수란 수가 무엇인지 처음부터 다시 공부를 진행했고, 공부를 하다 보니 소수를 구하는 여러 알고리즘들이 있다는 것을 알게 되었습니다. 그러다 저는 Miller-Rabin 이라는 소수 판별 알고리즘에 대해서 알게 되었고, 이 알고리즘을 포스트로 정리하는 작업을 진행했습니다. 해당 알고리즘의 개념을 알고 싶으신 분들은 Miller-Rabin 소수판별법 포스트를 참고해 주시길 바랍니다.
정답 코드
그럼 아래는 제가 구현한 Miller-Rabin 소수 판별법의 코드 입니다.
import random
def is_prime(n, k=5) :
# n 이 1보다 작거나 같으면 소수가 아니므로 False return
if n <= 1:
return False
if n <= 3: # n 이 3보다 작거나 같으면 2와 3 밖에 없으니 소수이므로 True return
return True
if n % 2 == 0: # 3보다 큰 n 이 2로 나누어 떨어지면 소수가 아니므로 False return
return False
r, d = 0, n-1
# 조건 검사를 위한 r와 d 를 구함
while d % 2 == 0:
d //= 2
r += 1
# 높은 신뢰도를 위해 k 번 실행 k의 값이 커질 수록 오류율이 1/4^k 만큼 줄어듦
for _ in range(k):
a = random.randrange(2, n-1) # 2~n-1 값 사이에 있는 랜덤 숫자를 선택
x= pow(a, d, n) # a^d 를 구하고 그 값을 mod n 을 진행
# x 가 1 이거나 n-1 이면 소수라고 보고 continue
if x == 1 or x == n-1:
continue
# 위 조건에서 소수 판별이 되지 않으면 두 번째 조건 판별을 진행
for _ in range(r-1):
x = pow(x, 2, n)
if x == n-1:
break
else: # 위 두 조건 모두 만족하지 못하면 False return
return False
# k 번 반복하는 동안 return 하지 않으면 소수라고 판단하고 True return
return True
m, n = map(int, input().split())
for i in range(m, n+1):
if is_prime(i, 5):
print(i)
위 코드 제출 결과 맞았습니다!! 를 확인할 수 있었습니다.
마치며
Baekjoon 에서 소수를 판별하는 문제를 풀어보았습니다. 해당 문제를 풀면서 알고리즘을 잘하긴 위해선 수학 이론 등을 많이 알아야 하지만 스스로 많이 부족하다는 것을 느꼈고, 좀 더 많이 공부를 해야겠구나 하는 생각도 들었습니다. 그리고 이 문제를 풀게 되면서 소수를 따로 구하는 여러 알고리즘들이 있다는 것을 알게 되었고, 이러한 알고리즘들을 배우면서 수학적 지식이 좀 더 늘어난 것 같습니다. 긴 글 읽어주셔서 감사드리며, 포스트 본문 내용 중에 잘못된 내용이나 오타, 궁금하신 사항이 있으시다면 댓글 달아주시기 바랍니다.
Comments