-
JUNGOL...44일지 2021. 2. 9. 09:01
Beginner_Coder/수학1/약수와 배수
문제
주어진 정수들 중 입력받은 수의 약수와 배수의 합을 각각 출력하라.
입력 형식
첫 줄에 정수의 개수 n (1<= n <=40)을 입력 받는다.
둘째 줄에는 n개의 정수를 한 줄에 입력 받는다.
셋째 줄에는 약수와 배수를 구할 정수 m(1<=m<=100)을 입력 받는다.
출력 형식
첫 줄에는 정수 m의 약수의 합을 둘째 줄에는 정수 m의 배수의 합을 출력한다.
입력 예
6
2 3 5 12 18 24
12출력 예
17
36
FactorAndMultiple.h
#include <iostream>FactorAndMultiple.cpp
void FactorAndMultiple::Code() { int n; int arr[40]; std::cin >> n; for (int i = 0; i < n; i++) { std::cin >> arr[i]; } int m; std::cin >> m; int sumOfFactor{ 0 }, sumOfMultiple{ 0 }; for (int i = 0; i < n; i++) { if (m % arr[i] == 0) { sumOfFactor += arr[i]; } if (arr[i] % m == 0) { sumOfMultiple += arr[i]; } } std::cout << sumOfFactor << '\n' << sumOfMultiple; }Beginner_Coder/수학1/약수 구하기
문제
어떤 자연수 p와 q가 있을 때, 만일 p를 q로 나누었을 때 나머지가 0이면 q는 p의 약수이다.
6을 예로 들면
6 ÷ 1 = 6 … 0
6 ÷ 2 = 3 … 0
6 ÷ 3 = 2 … 0
6 ÷ 4 = 1 … 2
6 ÷ 5 = 1 … 1
6 ÷ 6 = 1 … 0
그래서 6의 약수는 1, 2, 3, 6, 총 네 개이다.
두 개의 자연수 N과 K가 주어졌을 때, N의 약수들 중 K번째로 작은 수를 출력하는 프로그램을 작성하시오.
입력 형식
첫째 줄에 N과 K가 빈칸을 사이에 두고 주어진다.
N은 1 이상 10,000 이하이다. K는 1 이상 N 이하이다.
출력 형식
첫째 줄에 N의 약수들 중 K번째로 작은 수를 출력한다.
만일 N의 약수의 개수가 K개보다 적어서 K번째 약수가 존재하지 않을 경우에는 0을 출력하시오.
입력 예
6 3 | 25 4 | 2735 1
출력 예
3 │0 │1
Hint!
약수란? 어떤 수를 나누어 떨어지게 하는 수를 어떤 수의 약수라 한다.
즉, a * b = c일 경우 a와 b는 c의 약수가 된다.
1은 모든 수의 약수이며 자기 자신 또한 약수가 된다.
배수란? 어떤 수의 1배, 2배, 3배, 4배... 한 수를 어떤 수의 배수라 한다.
즉, a * b = c 일 경우 c는 a와 b의 배수가 된다.
자기 자신도 배수이며 배수의 개수는 무한하다.
프로그램에서 약수와 배수를 확인하기 위해서는 나머지 연산을 이용하면 된다.
a % b 가 0이면 a는 b의 배수이고, b는 a의 약수가 된다.
코드
for (i = 1; i <= N; i++) { if (N % i == 0) // i가 N의 약수이면 { cnt++; // 약수의 개수(cnt)를 증가한다. if (cnt == K) // 약수의 개수가 K개이면 { printf("%d\n", i); // K번째 약수인 i를 출력하고 return 0; // 프로그램을 종료한다. } } }코드분석
1부터 차례대로 N의 약수인지 확인하여 약수이면 cnt를 증가해 나가다가 cnt가 K와 같아지면 i를 출력하고 프로그램을 종료하도록 작성된 프로그램이다.
FindingFactor.h
#include <iostream>FindingFactor.cpp
void FindingFactor::Code() { int n, k; std::cin >> n >> k; for (int i = 1; i <= 10000; i++) { if (n % i == 0) { k--; if (k == 0) { std::cout << i; break; } } } if (k > 0) { std::cout << 0; } }Beginner_Coder/수학1/약수
문제
한 개의 정수를 입력받아 입력받은 정수의 약수를 모두 출력하는 프로그램을 작성하시오.
입력 형식
정수 N이 주어진다. (2 ≤ N ≤ 21억)
출력 형식
N의 약수를 작은 수부터 차례로 모두 출력한다.
입력 예
24
출력 예
1 2 3 4 6 8 12 24
Hint!
코드1
for (i = 1; i <= N; i++) { if (N % i == 0) { printf("%d ", i); } }코드분석
1부터 N까지 N의 약수인지 모두 확인하여 출력하는 프로그램이다.
그런데 위와 같이 작성하면 N이 21억이 입력이 되었을 때 1부터 21억까지 21억개의 수를 확인해 보아야 한다. 당연히 시간초과의 위험이 있으니 프로그램을 수정하여 시간을 줄여보도록 하자.
코드2
int sq; // N의 제곱근을 저장하기 위해 int arr[10000], cnt=0; // N의 약수를 저장하기 위해 scanf("%d", &N); sq = (int)sqrt(N); // N의 제곱근을 구하여 sq에 저장한다. for (i = 1; i <= sq; i++) { if (N % i == 0) { arr[cnt++] = i; // 작은수 저장 if (N / i != i) arr[cnt++] = N / i; // 큰수 저장 (작은수와 같지 않을 경우) } } // 이 부분에는 arr배열에 저장된 값을 정렬하여 모두 출력하도록 스스로 작성해보자.코드분석
위 프로그램은 N의 제곱근까지만 반복문을 실행해서 모든 약수를 구하는 프로그램이다.
만약 N이 100이라고 가정하고 100의 약수를 모두 구해보면 1 * 100 = 100 2 * 50 = 100 4 * 25 = 100 5 * 20 = 100 10 * 10 = 100 위와 같이 성립하므로 100의 약수는 1 2 4 5 10 20 25 50 100 이렇게 9개가 된다. 그런데 2가 100의 약수라는 것을 알게 된 순간 50이라는 약수도 구할 수 있게 된다.
즉, a * b = 100일 경우 a를 알게 되면 b를 구할 수 있다는 것이다. 그러므로 두 수의 곱이 N일 경우 그 두 수는 N의 약수이며 두 수중 작은 수의 범위는 1~(루트100) 이하가 된다.
위의 경우 10 * 10 = 100 이므로 10 이상의 수는 두 수의 곱으로 나타낼 경우 큰 수에 해당하므로 작은 수를 저장할 때 함께 저장이 되어 있는 것이다.
04 : sqrt는 제곱근을 구하는 함수이며 double형으로 리턴되므로 (int)를 붙여서 정수형으로 변환한 것이다.
08 : N이 100일 때 i가 10이면 작은 수와 큰 수가 모두 10이므로 작은 수 한 번만 저장하면 된다.
05 : 1부터 N의 제곱근까지 반복한다.
제곱근을 구하는 것이 번거롭다면 부등호의 양변을 제곱하여 아래와 같이 작성해도 된다.
for (i = 1; i * i <= N; i++)
Factors.h
#include <iostream> #include <vector> #include <algorithm> using std::vector;Factors.cpp
void Factors::Code() { int n; std::cin >> n; vector<int> factors; for (int i = 1; i * i <= n; i++) { if (n % i == 0) { factors.push_back(i); if (n / i != i) { factors.push_back(n / i); } } } std::sort(factors.begin(), factors.end()); for (int& factor : factors) { std::cout << factor << ' '; } }NadanKim/CodingTest_JUNGOL: JUNGOL 코딩 테스트를 위한 저장소 (github.com)
NadanKim/CodingTest_JUNGOL
JUNGOL 코딩 테스트를 위한 저장소. Contribute to NadanKim/CodingTest_JUNGOL development by creating an account on GitHub.
github.com