신기한 소수
| 시간제한 | 메모리 제한 | 제출 | 정답 | 맞힌사람 | 정답률 |
|---|---|---|---|---|---|
| 2 초 | 4 MB | 24265 | 11757 | 8319 | 45.921% |
문제
수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다.
7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수이고, 7도 소수이다. 즉, 왼쪽부터 1자리, 2자리, 3자리, 4자리 수 모두 소수이다! 수빈이는 이런 숫자를 신기한 소수라고 이름 붙였다.
수빈이는 N자리의 숫자 중에서 어떤 수들이 신기한 소수인지 궁금해졌다. N이 주어졌을 때, 수빈이를 위해 N자리 신기한 소수를 모두 찾아보자.
입력
첫째 줄에 N(1 ≤ N ≤ 8)이 주어진다.
출력
N자리 수 중에서 신기한 소수를 오름차순으로 정렬해서 한 줄에 하나씩 출력한다.
예제 입력 1 복사
4예제 출력 1 복사
2333
2339
2393
2399
2939
3119
3137
3733
3739
3793
3797
5939
7193
7331
7333
7393출처
알고리즘 분류
코드
package 신기한소수찾기;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static int N; // 입력(1이상 8이하의 범위)
static boolean isPrime(int num){
for(int i = 2; i<= (num / 2+1); i++){
if(num % i == 0)
return false;
}
return true;
}
static void DFS(int number){
if(String.valueOf(number).length() == N){
System.out.println(number);
}else{
for(int i = 1; i <= 10; i++){
if(i % 2 == 0)
continue;
if(isPrime(number * 10 + i))
DFS(number * 10 + i);
}
}
}
public static void main(String[] args) throws IOException {
// N = Integer.parseInt(br.readLine());
N = 4;
DFS(2);
DFS(3);
DFS(5);
DFS(7);
br.close();
}
}이 알고리즘은 주어진 자릿수(N)에 따라 신기한 소수를 찾는 문제입니다. 신기한 소수는 각 자릿수가 소수로 이루어진 소수입니다. 이 문제에서는 DFS(Depth-First Search, 깊이 우선 탐색)를 사용하여 재귀적으로 신기한 소수를 찾습니다. 다음은 이 코드의 각 부분에 대한 설명입니다.
주요 변수 및 함수
1. 변수
- BufferedReader br: 입력을 받기 위해 사용됩니다.
- int N: 주어진 자릿수(1 이상 8 이하의 범위).
2. 함수
- isPrime(int num): 주어진 숫자가 소수인지 판별하는 함수입니다.
- 소수가 아닌 경우 false를 반환하고, 소수인 경우 true를 반환합니다.
- DFS(int number): DFS 알고리즘을 사용하여 신기한 소수를 찾는 함수입니다.
isPrime 함수
이 함수는 입력된 숫자가 소수인지 확인합니다.
- 2부터 숫자의 절반까지(절반 + 1) 나누어 떨어지는지 확인합니다.
- 나누어 떨어지면 소수가 아니므로
false를 반환합니다. - 모든 조건을 통과하면 소쉬므로
true를 반환합니다.
static boolean isPrime(int num){
for(int i = 2; i <= (num / 2 + 1); i++){
if(num % i == 0)
return false;
}
return true;
}DFS함수
이 함수는 재귀적으로 호출되며, 현재 숫자의 자릿수를 늘려가면서 신기한 소수를 찾습니다.
- 현재 숫자의 자릿수가 N과 같아지면 해당 숫자를 출력합니다.
- 그렇지 않으면 1부터 9까지 홀수를 붙여 새로운 숫자를 만들고, 이 숫자가 소수인지 확인합니다.
- 소수이면 그 숫자를 가지고 다시 DFS 함수를 호출합니다.
static void DFS(int number){
if(String.valueOf(number).length() == N){
System.out.println(number);
} else {
for(int i = 1; i <= 10; i++){
if(i % 2 == 0)
continue;
if(isPrime(number * 10 + i))
DFS(number * 10 + i);
}
}
}
메인함수
프로그램의 시작점입니다. 초기 자릿수를 2, 3, 5, 7로 설정하여 DFS를 시작합니다. 이는 1자리 소수로서 다음 자릿수를 찾아나가기 위한 출발점이 됩니다.
public static void main(String[] args) throws IOException {
N = Integer.parseInt(br.readLine());
DFS(2);
DFS(3);
DFS(5);
DFS(7);
br.close();
}주요 동작
- main 함수에서 N을 입력받고 초기 소수 2, 3, 5, 7로 DFS를 시작합니다.
- DFS 함수는 현재 숫자의 자릿수를 확인하고, 자릿수가 N과 같아지면 숫자를 출력합니다.
- 그렇지 않으면 1부터 9까지 홀수를 붙여 새로운 숫자를 만들고 소수인지 확인합니다.
- 소수이면 그 숫자를 가지고 다시 DFS 함수를 호출합니다.
이 알고리즘은 재귀를 통해 모든 자릿수 조합을 탐색하며, 각 단계에서 소수 여부를 확인하여 신기한 소수를 찾습니다. N의 범위가 제한적이기 때문에 이 방법은 효율적으로 작동할 수 있습니다.
QnA
isPrime함수의 for문 조건문을 (i <= (num/2) + 1) 로 한 이유?
소수를 판별하기 위해 숫자의 절반까지 나누어 떨어지는지 확인하는 이유는, 소수의 성질과 약수의 성질을 고려한 것입니다. 다만, 실제로는 숫자의 제곱근까지만 확인해도 충분합니다. 이 부분을 더 명확하게 이해하기 위해 다음과 같이 설명할 수 있습니다:
소수의 정의
소수는 1과 자기 자신 외에는 나누어 떨어지지 않는 자연수입니다.
약수의 성질
어떤 수 n의 약수는 대칭적으로 나타납니다. 즉, n의 약수를 a * b = n이라고 할 때, a와 b는 n의 제곱근을 기준으로 대칭적으로 나타납니다.
예를 들어, n = 36일 때:
- 약수 쌍은
(1, 36), (2, 18), (3, 12), (4, 9), (6, 6)입니다. - 여기서
(6, 6)은 제곱근(6)에서 나타나며, 그 이후로는 대칭적으로 다시 나타나기 시작합니다.
따라서, 어떤 수 n이 소수인지 확인하려면 sqrt(n)까지만 나누어 떨어지는지 확인하면 됩니다. 이는 모든 약수 쌍 중 하나는 반드시 sqrt(n) 이하에 존재하기 때문입니다. 즉, a가 sqrt(n) 이하인 경우 b는 sqrt(n) 이상이 됩니다.
예시
예를 들어, n = 36의 제곱근은 6입니다. 36의 약수는 1, 2, 3, 4, 6, 9, 12, 18, 36이며, 6을 기준으로 대칭을 이룹니다. n이 2, 3, 4, 6으로 나누어 떨어지면 약수임을 알 수 있습니다.
코드 수정
이러한 이유로, 숫자의 절반까지 확인하는 대신 숫자의 제곱근까지만 확인하면 효율적으로 소수를 판별할 수 있습니다. 이를 코드로 수정하면 다음과 같습니다:
static boolean isPrime(int num) {
if (num < 2) return false; // 1과 1 이하의 숫자는 소수가 아님
for (int i = 2; i <= Math.sqrt(num); i++) {
if (num % i == 0)
return false; // 나누어 떨어지면 소수가 아님
}
return true; // 나누어 떨어지지 않으면 소수
}이렇게 하면 불필요한 검사를 줄여서 소수 판별의 효율성을 높일 수 있습니다. 제곱근까지만 확인하면 되기 때문에 시간 복잡도도 더 줄어듭니다.
코드 개선하기
for문의 조건이 i <= 10이라서 실제로 1부터 10까지 반복하고 있습니다. 그러나 i가 10인 경우는 의미가 없으므로 코드에서 제거해도 됩니다. 아래에서 더 자세히 설명하겠습니다.
코드 분석
코드의 DFS 메서드는 재귀적으로 자릿수를 늘려가면서 소수를 찾아내는 역할을 합니다. 코드를 다시 살펴봅시다:
static void DFS(int number){
if(String.valueOf(number).length() == N){
System.out.println(number);
} else {
for(int i = 1; i <= 10; i++){
if(i % 2 == 0) // 짝수는 무시
continue;
if(isPrime(number * 10 + i)) // 새로운 숫자가 소수인지 확인
DFS(number * 10 + i);
}
}
}반복문의 의미
for(int i = 1; i <= 10; i++)에서 i가 1부터 10까지 반복합니다. 하지만 실제로 소수를 만들기 위해 사용되는 숫자는 1부터 9까지의 홀수입니다. 이 부분을 i % 2 == 0 조건으로 짝수를 건너뛰고 있습니다.
잘못된 점
i <= 10조건은 실제로 10까지 포함하지만,i가 10인 경우는 홀수가 아니므로continue조건에서 제외됩니다.- 따라서,
i가 10인 경우는 소수 판별에 사용되지 않습니다.
수정 제안
for문 조건을 i <= 9로 변경하면 더 명확하게 표현됩니다. 이렇게 하면 i가 10일 때의 불필요한 검사를 피할 수 있습니다.
수정된 코드
static void DFS(int number){
if(String.valueOf(number).length() == N){
System.out.println(number);
} else {
for(int i = 1; i <= 9; i++){ // 1부터 9까지만 검사
if(i % 2 == 0) // 짝수는 무시
continue;
if(isPrime(number * 10 + i)) // 새로운 숫자가 소수인지 확인
DFS(number * 10 + i);
}
}
}코드 개선하기2
for 문 순회 시 홀수 값만 처리하도록 설정하면 if 조건에서 짝수 판별 여부를 검사하지 않아도 됩니다. 이렇게 하면 코드가 더 간결하고 효율적이 됩니다.
홀수 값만 순회하기 위해 for 문을 2씩 증가하도록 변경하면 짝수 검사를 하지 않아도 됩니다.
수정된 코드는 아래와 같습니다:
static void DFS(int number){
if(String.valueOf(number).length() == N){
System.out.println(number);
} else {
for(int i = 1; i <= 9; i += 2){ // 1부터 9까지 홀수만 검사
if(isPrime(number * 10 + i)) // 새로운 숫자가 소수인지 확인
DFS(number * 10 + i);
}
}
}이렇게 하면 for 문이 홀수 값만 순회하게 되어 if(i % 2 == 0) 조건이 필요 없게 됩니다. 이로 인해 코드가 더 깔끔하고 읽기 쉬워집니다.
'여러가지 > 알고리즘 & 자료구조' 카테고리의 다른 글
| [백준] 블랙잭 - 2798번 (0) | 2024.06.12 |
|---|---|
| 완전탐색 & 시뮬레이션 - 1 (0) | 2024.06.12 |
| [백준] 나이트의 이동 - 7562번 (1) | 2024.06.10 |
| [백준] 열 개씩 끊어 출력하기 - 11721번 (0) | 2024.06.01 |
| [백준] KMP는 왜 KMP일까? - 2902번 (0) | 2024.06.01 |