modern cpp challenge 책의 문제들을 푸는 과정을 작성해놓으려 한다.
1. 문제
2. 풀이(1)
2.1. I/O
2.2. 연산
2.3. 코드
3. 코드 수정
3.1. I/O 타입
3.2. 연산 방법
3.3. 구현
3.4. 결론
4. 결론
1. 문제
소인수 분해 프로그램 구현하기
사용자가 입력한 수의 소인수들을 출력하는 프로그램을 작성하라. 단, 입력값은 양의 정수로 제한한다.
2. 풀이(1)
필요한 코드 구조는 아래와 같다.
입력 받는 부분 + 소인수를 구하는 부분 + 소인수 출력하는 부분
2.1. I/O
소인수는 약수 중 소수인 수들을 말하며, 양의 정수의 약수들은 전부 양수이므로 양의 정수의 합 역시 양수이다.
그러므로 양의 정수로 값이 정해져 있고, 1.0 * 10^6이 범위로 설정되어 때문에 입력값, 출력값을 양의 정수라는 것을 명시한다는 의미로 unsigned int로 설정할 것이다.
2.2. 연산
약수들을 먼저 구한 다음 약수에 대해 소수 판별을 할 것이다. 그러므로 입력값이 주어졌을 때 해당 입력값까지 데이터값을 bool로 가지는 벡터에 소수 판별을 미리 해 놓는다. (입력값이 일정하지 않으므로 동적 메모리로 처리할 수 있는 벡터를 사용한다.)
그리고 약수를 구하면서 해당 약수를 벡터의 인덱스로 처리하여 해당 값이 소수인지 아닌지 판단한다.
2.3. 코드
처음에 작성한 코드는 아래와 같다.
#include <iostream>
#include <vector>
void set_prime(unsigned int n, std::vector<bool>& is_prime) {
for(unsigned int i = 2; i * i <= n; ++i) {
if(is_prime[i]) {
for(unsigned int j = i * i; j < n; j += i)
{
is_prime[j] = false;
}
}
}
}
void get_prime_factor(unsigned int n, std::vector<bool>& is_prime) {
for(unsigned int i = 2; i * i <= n; ++i) {
if(n % i == 0) {
if(is_prime[i]) {
std::cout << i << '\n';
}
if(is_prime[n / i]) {
std:: cout << n / i << '\n';
}
}
}
}
int main() {
unsigned int n;
std::cin >> n;
std::vector<bool> is_prime(n + 1, true);
set_prime(n, is_prime);
get_prime_factor(n, is_prime);
}소수를 구하는 배열을 세팅하고, 해당 배열에 약수들을 넣어보며 소수인지 아닌지 판단했다. 그리고 약수 전체를 판정해야 하기 때문에 i가 약수일 경우 n/i도 약수여서 해당 값도 점검하도록 설정했다.
시간복잡도는 O(nlog(log(n))이다.
3. 코드 수정
핵심 로직을 수정하려고 한다.
3.1. I/O
입출력 부분은 크게 수정하지 않았다.
3.2. 연산 방법
에라토스테네스의 체로 소수를 판별하는 것이 아니라 나누는 값을 홀수, 짝수로 각각 나눠 경우의 수를 파악한다.
3.3. 구현
연산 방법을 수정하면서 수정했는데, 해당 부분은 결론 부분에 서술하겠다.
3.4. 결론
수정한 전체 코드는 아래와 같다.
#include <iostream>
void get_prime_factor(unsigned int n) {
if(n <= 1)
return;
while(n % 2 == 0) {
std::cout << 2 << '\n';
n /= 2;
}
for(unsigned int i = 3; i * i <= n; i = i + 2) {
if(n % i == 0) {
std::cout << i << '\n';
n /= i;
}
}
if(n > 1)
std::cout << n << '\n';
}
int main() {
unsigned int n;
std::cin >> n;
get_prime_factor(n);
}처음에 2로 나눠서 짝수인지 여부를 판별하고, 2로 나눈 수를 다시 3부터 짝수로 나눠서 소인수를 판별한다.
그리고 남은 값이 1보다 클 경우 처음 수가 소수라는 의미이므로 처음 수 그대로 출력한다.
시간복잡도는 O(sqrt(n))이다.
4. 후기
단순히 이전에 풀었던 방법을 적용하는 것보다 일단 연산하는 방법이 시간복잡도상 더 효율적일 수 있다는 사실을 알았다. 각각 예외 케이스별로 나누고, 홀수/짝수 나눠서 푸는 방법은 기억해 놔야겠다.