파이썬 코딩테스트 강좌, 소수 & 팰린드롬 수 중에서 최솟값 찾기

안녕하세요, 코딩테스트 준비생 여러분! 오늘은 소수(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 primes

2단계: 팰린드롬 수 확인하기

소수를 찾았다면, 이제 이들 중에서 팰린드롬 수를 찾아야 합니다. 팰린드롬 수는 정방향과 역방향이 동일한 수를 의미합니다. 예를 들어, 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}")

결론

이번 강좌를 통해 소수와 팰린드롬 수의 개념을 이해하고, 이를 활용하여 문제를 푸는 방법을 연습하였습니다. 소수를 찾는 에라토스테네스의 체와 숫자가 팰린드롬인지 확인하는 간단한 알고리즘을 통해 효율적인 코드를 작성할 수 있었습니다. 주어진 문제를 통해 알고리즘적 사고와 코딩 실력을 한 단계 발전시키길 바랍니다.

향후 더욱 다양한 문제를 함께 풀어보며, 코딩테스트 준비에 힘쓰도록 해요. 감사합니다!