안녕하세요, 코딩테스트 준비생 여러분! 오늘은 소수(prime number)와 팰린드롬 수(palindrome number)를 활용하여 주어진 범위에서 두 조건을 동시에 만족하는 수 중 최솟값을 찾는 문제를 풀어보겠습니다. 이 문제는 알고리즘 문제 풀이에서 자주 등장하는 주제 중 하나로, 효율적인 코드를 짜는 데 많은 도움이 됩니다. 그럼 문제를 함께 살펴보겠습니다.
문제 정의
다음과 같은 조건을 만족하는 최솟값을 찾는 함수를 작성하세요:
- 주어진 자연수
N이 입력으로 주어질 때,1 <= N <= 10,000. N이하의 소수 중에서 팰린드롬인 수를 찾습니다.- 찾은 소수 중 최솟값을 반환합니다.
예를 들어, N = 31인 경우, 소수는 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31이고, 이 중 팰린드롬인 수는 2, 3, 5, 7, 11입니다. 따라서 11이 최솟값이 됩니다.
문제를 푸는 과정
문제를 해결하기 위해 다음과 같은 단계로 진행하겠습니다:
- 1단계: 주어진
N이하의 소수를 찾는 함수를 정의합니다. - 2단계: 찾은 소수들 중 팰린드롬인 수를 확인합니다.
- 3단계: 팰린드롬인 소수들 중 최솟값을 반환합니다.
1단계: 소수 찾기
소수를 찾기 위해 에라토스테네스의 체 알고리즘을 사용할 것입니다. 이 알고리즘은 효율적으로 소수를 찾는 방법 중 하나로, 시간 복잡도가 O(n log log n)입니다. 이를 통해 주어진 N 이하의 모든 소수를 찾아낼 수 있습니다.
에라토스테네스의 체 알고리즘 구현
def sieve_of_eratosthenes(n):
primes = []
is_prime = [True] * (n + 1)
is_prime[0], is_prime[1] = False, False
for i in range(2, int(n**0.5) + 1):
if is_prime[i]:
for j in range(i * i, n + 1, i):
is_prime[j] = False
for i in range(n + 1):
if is_prime[i]:
primes.append(i)
return primes2단계: 팰린드롬 수 확인하기
소수를 찾았다면, 이제 이들 중에서 팰린드롬 수를 찾아야 합니다. 팰린드롬 수는 정방향과 역방향이 동일한 수를 의미합니다. 예를 들어, 121과 12321는 팰린드롬입니다. 이를 확인하는 함수는 다음과 같을 것입니다:
def is_palindrome(num):
return str(num) == str(num)[::-1]3단계: 최솟값 반환하기
마지막으로, 찾은 팰린드롬 수 중에서 최솟값을 찾아 반환하는 함수를 작성합니다. 최솟값을 쉽게 구하기 위해 min() 함수를 사용할 수 있습니다.
def find_smallest_palindrome_prime(n):
primes = sieve_of_eratosthenes(n)
palindrome_primes = [p for p in primes if is_palindrome(p)]
if not palindrome_primes:
return None # 팰린드롬 수가 없을 경우 None 반환
return min(palindrome_primes)전체 코드
위의 모든 단계를 종합하였을 때, 최종 코드는 다음과 같습니다:
def sieve_of_eratosthenes(n):
primes = []
is_prime = [True] * (n + 1)
is_prime[0], is_prime[1] = False, False
for i in range(2, int(n**0.5) + 1):
if is_prime[i]:
for j in range(i * i, n + 1, i):
is_prime[j] = False
for i in range(n + 1):
if is_prime[i]:
primes.append(i)
return primes
def is_palindrome(num):
return str(num) == str(num)[::-1]
def find_smallest_palindrome_prime(n):
primes = sieve_of_eratosthenes(n)
palindrome_primes = [p for p in primes if is_palindrome(p)]
if not palindrome_primes:
return None
return min(palindrome_primes)
# 예시 사용
N = 31
result = find_smallest_palindrome_prime(N)
print(f"{N} 이하의 소수 중 팰린드롬 수의 최솟값은: {result}")결론
이번 강좌를 통해 소수와 팰린드롬 수의 개념을 이해하고, 이를 활용하여 문제를 푸는 방법을 연습하였습니다. 소수를 찾는 에라토스테네스의 체와 숫자가 팰린드롬인지 확인하는 간단한 알고리즘을 통해 효율적인 코드를 작성할 수 있었습니다. 주어진 문제를 통해 알고리즘적 사고와 코딩 실력을 한 단계 발전시키길 바랍니다.
향후 더욱 다양한 문제를 함께 풀어보며, 코딩테스트 준비에 힘쓰도록 해요. 감사합니다!