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

오늘은 취업 준비생들에게 자주 출제되는 알고리즘 문제 중 하나인 ‘소수 및 팰린드롬 수 중에서 최솟값 찾기’에 대해 깊게 알아보겠습니다. 이 문제를 통해 우리는 소수와 팰린드롬의 개념을 복습하고, C++을 통해 알고리즘을 구현해보는 시간을 가지겠습니다.

문제 설명

주어진 정수 N이 있습니다. 이때 N보다 크거나 같고, N보다 작거나 같은 범위 내에서 소수이면서 팰린드롬인 정수 중에서 최솟값을 찾는 문제입니다.

예시

N = 10 일 경우, 소수 및 팰린드롬 수는 11 입니다.
N = 30 일 경우, 소수 및 팰린드롬 수는 31 입니다.
N = 100 일 경우, 소수 및 팰린드롬 수는 101 입니다.

문제 접근 방법

소수는 1보다 큰 정수 중 1과 자기 자신 이외의 약수를 가지지 않는 자연수입니다. 팰린드롬 수는 앞뒤에서 읽어도 동일한 수를 의미합니다. 예를 들어, 121, 12321 등이 있습니다.

문제를 해결하기 위해 다음의 단계를 따를 것입니다:

N부터 시작하여 모든 수를 검사합니다.
각 숫자에 대해 소수인지 확인합니다.
소수인지 확인 후, 팰린드롬인지 확인합니다.
모든 조건을 만족하는 최솟값을 찾아 반환합니다.

C++ 구현

이제 C++ 언어를 사용하여 이 문제를 해결하는 코드를 작성해보겠습니다.

코드 설명


#include 
#include 
#include 

using namespace std;

// 소수 판별 함수
bool isPrime(int num) {
    if (num < 2) return false;
    for (int i = 2; i <= sqrt(num); ++i) {
        if (num % i == 0) return false;
    }
    return true;
}

// 팰린드롬 판별 함수
bool isPalindrome(int num) {
    string str = to_string(num);
    int len = str.length();
    for (int i = 0; i < len / 2; ++i) {
        if (str[i] != str[len - i - 1]) return false;
    }
    return true;
}

// N보다 크거나 같은 소수 및 팰린드롬의 최솟값을 찾는 함수
int findMinPrimePalindrome(int N) {
    for (int i = N; ; ++i) {
        if (isPrime(i) && isPalindrome(i)) {
            return i;
        }
    }
}

int main() {
    int N;
    cout << "정수 N을 입력하세요: ";
    cin >> N;
    
    int result = findMinPrimePalindrome(N);
    cout << "최솟값: " << result << endl;
    
    return 0;
}

코드 설명

위 코드를 통해 다음과 같은 과정을 거쳐 원하는 결과를 얻을 수 있습니다:

isPrime 함수: 주어진 정수가 소수인지 판별합니다. 2 이상인 숫자만 판별하고, 2부터 sqrt(num)까지 나누어 떨어지는 숫자가 있는지 확인합니다.
isPalindrome 함수: 주어진 정수가 팰린드롬인지 판별합니다. 숫자를 문자열로 변환 후, 앞에서부터와 뒤에서부터 비교하여 일치하는지 확인합니다.
findMinPrimePalindrome 함수: 주어진 N부터 시작하여 모든 숫자에 대해 소수 및 팰린드롬 여부를 확인합니다. 소수이자 팰린드롬인 숫자를 발견하면 바로 반환합니다.
main 함수: 사용자로부터 정수 N을 입력받고, 이를 기반으로 최솟값을 찾아 출력합니다.

이해를 돕기 위한 예제

예를 들어 N=10인 경우, 함수는 10부터 시작하여 10, 11을 확인합니다. 11은 소수이며 팰린드롬이므로 최솟값으로 11을 반환합니다.

시간 복잡도

우리가 작성한 알고리즘의 시간 복잡도는 입력 값 N에 따라 달라집니다. 소수 판별시 sqrt(N)만큼의 시간이 소요되며, 전체적으로 N에서 시작해 최솟값을 찾는 과정까지 포함하면 최악의 경우 O(N√N)의 시간 복잡도를 가집니다.

푸는 과정에서 주의할 점

소수 및 팰린드롬 수를 찾는 과정에서 기본적인 수학과 문자열 변환에 대한 이해가 필요합니다. 또한, C++의 기본 문법 및 자료형에 대한 이해도 필수적입니다. 이 문제를 해결하기 위해 정보를 잘 정리하고, 단계별로 접근하는 연습이 필요합니다.

맺음말

이번 강좌를 통해 소수와 팰린드롬 관련 알고리즘을 이해하고 스스로 구현해보는 기회를 가졌습니다. 이 문제는 실무에서 활용될 수 있는 유용한 알고리즘 중 하나로, 취업 준비 시 유용하게 활용할 수 있습니다. 앞으로도 다양한 알고리즘 문제를 풀어보며 코딩 테스트를 준비해나가길 바랍니다.