개요
이 튜토리얼에서는 주어진 수가 k-거친 수(k-rough number) 또는 k-재그드 수(k-jagged number)인지 판별하는 프로그램을 C++로 작성해 보겠습니다.
가장 작은 소인수가 주어진 값 k보다 크거나 같은 수를 k-거친 수 또는 k-재그드 수라고 부릅니다. 예를 들어 75 = 3 × 5 × 5이므로 가장 작은 소인수는 3이고, k가 3일 때 75는 3-거친 수가 됩니다.
문제 해결 접근 방법
이 문제는 다음 단계를 거쳐 해결할 수 있습니다.
- 두 수 n과 k를 초기화합니다.
- n의 모든 소인수를 찾아 벡터(vector)에 저장합니다.
- 벡터의 첫 번째 요소, 즉 가장 작은 소인수를 k와 비교하여 n이 k-거친 수인지 판별합니다.
구현 예제
위 접근 방법을 코드로 구현하면 다음과 같습니다.
#include <bits/stdc++.h>
using namespace std;
bool isPrime(int n) {
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
vector<int> getPrimes(int n) {
vector<int> primes;
for (int i = 2; i < n; i++) {
if (n % i == 0 && isPrime(i)) {
primes.push_back(i);
}
}
return primes;
}
bool isRoughNumber(int n, int k) {
vector<int> primes = getPrimes(n);
return primes[0] >= k;
}
int main() {
int n = 75, k = 3;
if (isRoughNumber(n, k)) {
cout << n << " is a " << k << " rough number" << endl;
} else {
cout << n << " is not a " << k << " rough number" << endl;
}
return 0;
}
실행 결과
위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.
75 is a 3 rough number
75의 가장 작은 소인수는 3이고, 이 값이 k(=3)보다 크거나 같으므로 75는 3-거친 수로 판별됩니다.
최적화된 접근 방법
사실 모든 소인수를 벡터에 저장할 필요는 없습니다. n의 가장 작은 소인수 하나만 찾아 k와 바로 비교하면 되기 때문입니다. 이렇게 하면 불필요한 저장 공간과 연산을 줄여 시간·공간 복잡도를 모두 개선할 수 있습니다.
bool isRoughNumber(int n, int k) {
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
return i >= k; // 가장 작은 소인수를 발견하면 즉시 비교
}
}
return n >= k; // n 자체가 소수인 경우
}
2부터 √n까지 순회하며 처음으로 나누어 떨어지는 수가 곧 가장 작은 소인수이므로, 별도의 소수 판별 함수나 벡터 없이도 동일한 결과를 훨씬 효율적으로 얻을 수 있습니다.
마무리
이번 튜토리얼에서는 k-거친 수의 개념과 이를 판별하는 C++ 코드를 살펴보았습니다. 기본 구현에서 한 단계 더 나아가, 가장 작은 소인수만 찾는 최적화된 방법까지 직접 구현해 보시기 바랍니다. 튜토리얼에 대해 궁금한 점이 있다면 댓글로 남겨 주세요.