[synergy 요청] codeup 1284번 암호 해독 문제 풀이
CodeUp 1284번
01. 문제 정의 ☝️
문제 설명
두 소수의 곱을 암호로 사용하는 알고리즘은 큰 수의 소인수분해가 어렵기 때문에 안전하다고 알려져있다.
그렇지만, 만약 두 소수를 잊어버리면 어떻게 될까? 굉장히 난감할 것이다.
이에 대비해 어떤 수(n)가 입력되면 두 소수의 곱으로 나타낼 수 있으면 두 소수를 오름차순으로 출력하고,
그렇지 않으면 “wrong number”를 출력하는 프로그램을 작성하시오.
입력
어떤 수 n이 입력된다.(단, 1<=n<=10,000,000)
출력
n을 두 소수의 곱으로 나타낼 수 있으면 두 수를 오름차순으로 출력한다.
(단, 가능한 소수 중 가장 작은 소수와의 곱으로 나타낸다.)
하고, 그렇지 않으면 “wrong number”를 출력한다.
입력 예시
21
출력 예시
3 7
이전 글에서 입력 / 처리 / 출력 부분으로 나누어 문제를 해결하는 코딩 방법을 소개해드렸습니다. 위의 문제도 읽어보면 어렵게 느껴지실텐데 쉽게 풀어보는 시간을 가져보겠습니다.
02.1. 입력 👇
먼저 가장 쉬운 부분 ‘입력’ 부분에 대한 코드를 작성해보겠습니다. 문제를 읽어보니 입력은 하나밖에 없습니다. 간단하게 num이라는 변수를 만들어서 입력받아보겠습니다.
#include <stdio.h>
int main(void) {
int num;
scanf("%d", &num);
입력에 대한 코드는 구현되었습니다. 여기까지는 쉽게 생각하셨을텐데요. 어렵게 느끼셨던 처리를 어떻게 해결할 지에 대한 아이디어를 생각해보겠습니다.
02.2. Idea! 👇
일단 문제를 분석해보겠습니다. 코딩을 시작하기 전에 항상 문제를 정확하게 이해하고 처리 방법을 글로 써보는 것이 중요합니다. 해당 문제는 어떤 임의의 숫자를 소수의 곱으로 나타낼 수 있으면 두 개의 소수를 출력하고 그렇지 않으면 “wrong number”를 출력하는 문제입니다.
그럼 첫 번째 소수에 대한 개념부터 알고 넘어가야 할 것 같습니다. 소수는 아시는 분은 당연히 아시겠지만 양의 약수가 단 두 개 뿐인 수를 의미합니다. 정의를 내려보면 ‘1과 자기 자신으로 밖에 나누어 떨어지지 않고 자기 자신의 곱셉의 역수가 없는 수’라고 합니다. (참고 : 나무위키) 여기서 한가지 더 알아야 할 것은 1은 소수가 아닙니다!
이 정도의 개념을 이해하셨으면 이제 문제를 어떻게 풀어볼지 생각해보겠습니다. 예를 들어 21이라는 수가 입력되었을 때 어떻게 3과 7을 찾아낼 수 있을까요? 먼저는 21을 어떤 수의 곱으로 만들어보아야 할 것입니다. 첫번째로 21은 1과 21의 곱으로 표현할 수 있습니다. 또 3과 7의 곱으로 나타낼 수 있죠. 이 외에는 정수의 곱으로는 더이상 나타낼 수 없습니다. 이해를 좀 더 돕기 위해 다른 예제도 한 번 생각해볼까요? 40이라는 수를 어떤 수의 곱으로 만들어 보겠습니다. 40은 1과 40, 2와 20, 4와 10, 5와 8의 곱으로 나타낼 수 있습니다. 또 다른 예를 들어볼까요? 35의 숫자를 어떤 수의 곱으로 만들어 보겠습니다. 35는 1과 35, 5와 7의 곱으로 나타낼 수 있습니다.
제가 지금 계속 반복해서 다른 예를 들어보고 있는데요. 너무 쉽게 느껴지셨다면 위의 예제들의 규칙을 한번 찾아보시길 바랍니다. 알고리즘 문제를 해결할 때 가장 기본적인 부분이 바로 이 규칙을 찾는 것이기 때문에 규칙을 찾을 때까지 다른 예제를 들어 찾아보셔야 합니다. 당연히 우리는 구구단을 외우고 있기 때문에 35라는 숫자를 보면 5와 7의 곱으로 이해할 수 있지만 구구단을 모르는 아이에게 35를 어떤 수의 곱으로 나타낼 수 있는 것을 가르치는 것은 쉽지 않을 것입니다.
앞에서 규칙을 찾으신 분들은 한 번 제가 생각한 규칙과 맞는지 맞춰보시길 바랍니다.
- 임의의 수를 1로 나누면 몫이 임의의 수가 나올 것이기 때문에 1과 몫(임의의 수)으로 임의의 수를 나타낼 수 있다.
- 임의의 수를 2로 나누어 나머지가 0이 되면 2와 몫으로 임의의 수를 나타낼 수 있다.
- 임의의 수를 3으로 나누어 나머지가 0이라면 3과 몫으로 임의의 수를 나타낼 수 있다.
- 임의의 수를 4로 나누어 나머지가 0이라면 4와 몫으로 임의의 수를 나타낼 수 있다.
- 이러한 반복을 임의의 수의 크기만큼 돌려본다.
이렇게 규칙을 찾아냈다면 코드로 한 번 구현해보겠습니다.
for(int i = 1; i <= num; ++i) {
if(num%i == 0)
printf("%d %d", i, num/i);
}
이렇게 임의의 수에 대한 두 수의 곱을 찾아 냈습니다. 이제 남은 건 찾은 두 수의 곱이 소수라는 조건만 있으면 되겠죠?
소수는 1과 자기 자신만을 약수로 가지는 수이기 때문에 2로 나누었을 때 나누어 떨어지면 소수가 아닙니다. 3으로 나누었을 때도 나누어 떨어지면 소수가 아니겠죠?
예를 들어 35를 기준으로 소수인지 아닌지 찾아보겠습니다. 35는 2로 나누었을 때 나누어 떨어지지 않습니다. 3으로도 나누어 떨어지지 않습니다. 4로도 나누어 떨어지지 않습니다. 그렇지만 5로는 7로 나누어 떨어집니다.
한가지 더 예제를 들어볼까요? 121이 소수인지 알아보겠습니다. 121은 2로 나누었을 때 나누어 떨어지지 않습니다. 3으로도 나누어 떨어지지 않습니다. 4으로도 나누어 떨어지지 않습니다. 5으로도 나누어 떨어지지 않습니다. 6으로도 나누어 떨어지지 않습니다. 7으로도 나누어 떨어지지 않습니다. 8으로도 나누어 떨어지지 않습니다. 9으로도 나누어 떨어지지 않습니다. 10으로도 나누어 떨어지지 않습니다. 그렇지만 11로는 11로 나누어 떨어집니다.
마지막으로 하나 더 예제를 들어보겠습니다. 11이 소수인지 아닌지 알아보겠습니다. 11은 2로 나누었을 때 나누어 떨어지지 않습니다. 3으로도 나누어 떨어지지 않습니다. 4으로도 나누어 떨어지지 않습니다. 5으로도 나누어 떨어지지 않습니다.
그런데 여기서 6으로 나누어 볼 필요가 있을까요? 5부터는 나누었을 때 몫이 2, 나머지가 1로 나누어집니다. 그런데 6부터는 나누었을 때 몫이 1, 나머지가 5로 6보다 커지면 나누어 볼 필요가 없어집니다. 반복 횟수는 임의의 수 / 2 보다 작을 때까지만 반복해보면 된다는 점을 알 수 있습니다.
이렇게 11은 11/2의 몫은 5이므로, 5까지 나누어보았을 때 나누어 떨어지지 않으면 소수가 됩니다.
이렇게 소수를 판별하는 예제를 몇가지 들어서 확인해보았습니다. 코드로 구현해보겠습니다.
int i;
for(i = 2; i <= num/2; ++i) {
if(num%i == 0) // 반복 중에 한번이라도 조건이 만족되면 소수가 아님
break;
}
// 반복을 모두 빠져나왔는데도 조건에 걸리지 않았으면 소수
if(i == num/2 + 1)
// 소수
else
// 소수가 아님
이렇게 코드를 구현해보았습니다. 아이디어를 찾고 코드로 구현하는 정도는 여기까지면 충분합니다. 이제 만들어진 코드를 이용해서 두 수의 곱이 소수인지 아닌지를 판별하는 문제를 해결해보도록 하겠습니다.
02.3. 처리 / 출력 👇
일단 위에서 입력된 수는 임의의 변수 num로 받았습니다.
위에서 구현한 두 개의 코드를 합쳐서 문제를 해결해보겠습니다. 입력된 수 num을 두 개의 곱으로 나타낸 뒤 두개의 값을 모두 소수인지 아닌지 판단해서 두 수가 모두 소수이면 값을 출력하고 없으면 “wrong number”를 출력하도록 하겠습니다.
#include <stdio.h>
int main(void) {
int num;
scanf("%d", &num);
for(int i = 1; i <= num; ++i) {
if(num%i == 0)
printf("%d %d", i, num/i);
}
return 0;
}
먼저 두 수의 곱으로 나타내보았습니다. 예를 들어 21을 입력하면 1과 21, 3과 7, 7과 3, 21과 1이 출력되게 됩니다. 하지만 우리는 소수의 조건으로 1이 필요 없음을 알고 있습니다. 그래서 변수 i의 값을 1이 아닌 2부터 증가시키는 것이 좀 더 효율적이라는 것을 알 수 있습니다. 이제 뽑힌 두 수 ( i 와 num/i )의 값을 소수인지 아닌지를 확인해보는 코드를 추가해보겠습니다.
#include <stdio.h>
int main(void) {
int num;
scanf("%d", &num);
for(int i = 2; i <= num; ++i) {
if(num%i == 0) {
int j;
for(j = 2; j <= (i)/2; ++j) { // i 가 소수인지 아닌지 확인
if((i)%j == 0)
break;
}
int k;
for(k = 2; k <= (num/i)/2; ++k) { // num/i가 소수인지 아닌지 확인
if((num/i)%k == 0)
break;
}
if(j == i/2 + 1 && k == (num/i)/2 + 1) {// 반복문이 끝까지 돌았을 조건
printf("%d %d", i, num/i);
return 0;
}
}
}
printf("wrong number");
return 0;
}
자 이렇게 idea 를 구현했던 코드들을 합쳐서 문제를 해결하는 코드를 만들어 보았습니다. 그렇지만 여기서 끝을 내기에는 가독성이 떨어져서 코드가 이쁘지가 않네요. 🙄🙄🙄
가장 기초적인 방법으로 문제를 풀었긴 했지만 그래도 사용자 정의 함수를 저희는 배웠으니 함수를 만들어서 조금 더 이쁘게 가다듬어 보겠습니다. 사용자 정의 함수도 반복문과 마찬가지로 반복되는 코드를 함수로 만들어 코드를 간략하게 하고 가독성을 높이는 장점이 있습니다. 인자 전달의 오버헤드가 발생되기는 하지만 가독성 측면에서 위와 같을 때는 사용하는 것이 좋습니다. 그럼 반복되는 코드들을 먼저 찾아 보겠습니다!
찾으셨나요? 이렇게 찾으셨으면 정답입니다.
int j;
for(j = 2; j <= (i)/2; ++j) { // i 가 소수인지 아닌지 확인
if((i)%j == 0)
break;
}
int k;
for(k = 2; k <= (num/i)/2; ++k) { // num/i가 소수인지 아닌지 확인
if((num/i)%k == 0)
break;
}
() 안에 들어가 있는 수만 달라지는 것이 보이시나요? 이렇게 되면 이 괄호 안에 들어가는 값을 인자로 전달 받는 함수를 만들면 됩니다. 함수의 이름은 개발자가 정의하는 것인데 저는 소수를 판별하는 함수이기 때문에 isPrimeNum라고 정의해보겠습니다.
int isPrimeNum(int num) {
for(int i = 2; i <= num/2; ++i)
if(num%i == 0)
return 0;
return 1;
}
이렇게 만들고 보니 이 함수는 인자로 받은 num라는 변수가 소수이면 1(True), 소수가 아니면 0(False)를 반환하는 함수가 됐습니다. 그럼 이 함수를 응용해서 main 문을 어떻게 바꿀 수 있는지 바꿔보겠습니다!
#include <stdio.h>
int isPrimeNum(int num) {
for(int i = 2; i <= num/2; ++i)
if(num%i == 0)
return 0;
return 1;
}
int main(void) {
int num;
scanf("%d", &num);
for(int i = 2; i <= num; ++i) {
if(num%i == 0) {
if (isPrimeNum(i) && isPrimeNum(num/i)) {
printf("%d %d", i, num/i);
return 0;
}
}
}
printf("wrong number");
return 0;
}
이렇게 바꿔보았습니다. 훨씬 간단해지고 가독성이 높아진게 보이시나요? 😄
그렇지만 이렇게 바꾸고 나니 오류가 보입니다. 바로 i는 1이 될 수 없지만 num/i 의 값은 1이 될 수도 있기 때문입니다. 그래서 if 문의 조건에 num/i가 1이 아니라는 조건을 하나 더 넣겠습니다.
#include <stdio.h>
int isPrimeNum(int num) {
for(int i = 2; i <= num/2; ++i)
if(num%i == 0)
return 0;
return 1;
}
int main(void) {
int num;
scanf("%d", &num);
for(int i = 2; i <= num; ++i) {
if(num%i == 0) {
if (isPrimeNum(i) && isPrimeNum(num/i) && num/i != 1) {
printf("%d %d", i, num/i);
return 0;
}
}
}
printf("wrong number");
return 0;
}
자! 완성되었습니다. 기본적인 아이디어를 이용해서 코드로 구현을 했고 구현된 코드를 사용자 정의 함수를 이용해서 가독성을 높여보았습니다. 만들어진 코드를 보시면 어렵게 보이실 수 있지만 과정을 하나하나 차근차근 따라가보시면 그렇게 어렵지 않은 내용임을 알 수 있습니다.
코드를 구현할 때 너무 어렵고 거창하게 만드실 필요는 없습니다. 구현이 우선이고 코드를 간략화하는 일이나 라이브러리 함수를 사용하는 것은 이후에 변경하셔도 괜찮습니다.
최대한 어렵지 않게 이해시켜드리려고 노력했는데 잘 이해되셨나요? 어려운 부분이 있었다면 댓글 남겨주시고 제가 혹시 설명 중 잘못된 부분이나 실수한 부분이 있으면 댓글 남겨주시면 바로 수정하거나 답변드리겠습니다! 다들 컨디션 조절 잘하시고 끝까지 열심히 공부해서 좋은 결과 있기를 바랍니다! 😄👏
댓글