백준 단계 9 : 약수, 배수와 소수 (C++)

5086. 두 수가 주어졌을 때, 다음 3가지 중 어떤 관계인지 구하는 프로그램을 작성하시오.

#include<iostream>
#include<cmath>
using namespace std;
int main() {
    ios::sync_with_stdio;
    cin.tie(0);
    int x, y;
    while(1)
    {
        cin >> x >> y;
        if (x == 0 && y == 0)
            break;

        if (y % x == 0)
        {
            cout << "factor\n";
        }
        else if (x % y == 0) {
            cout << "multiple\n";
        }
        else {
            cout << "neither\n";
        }
    };
    
    return 0;
}

연산자 %를 쓰는 간단한 문제이다. 

 

 

 

2501. 두 개의 자연수 N과 K가 주어졌을 때, N의 약수들 중 K번째로 작은 수를 출력하는 프로그램을 작성하시오.

#include<iostream>
#include<cmath>
using namespace std;
int main() {
    ios::sync_with_stdio;
    cin.tie(0);
    int n, k, i = 1, count = 1;
    cin >> n >> k;

    while (k != count) {
        i++;
        if (i > n) {
            i = 0;
            break;
        }
        if (n % i == 0) {
            count++;
        }  
    }
    cout << i;
    return 0;
}

이 문제도 %를 안다면 쉽게 풀 수 있었다. 다들 배열로 풀던데 굳이 모든 약수를 저장할 필요가 없을 것 같아서 난 배열을 사용하지 않았다.

 

 

 

 

9506. 어떤 숫자 n이 자신을 제외한 모든 약수들의 합과 같으면, 그 수를 완전수라고 한다. 예를 들어 6은 6 = 1 + 2 + 3 으로 완전수이다.

#include<iostream>
#include<cmath>
using namespace std;
int main() {
    ios::sync_with_stdio;
    cin.tie(0);
    int n, k = 1, sum = 1;
    int divisor[100000] = {1, };
    while (1) {
        cin >> n;
        if (n == -1)
            break;
        for (int i = 2; i < n; i++)
        {
            if (n % i == 0) {
                divisor[k] = i;
                sum += i;
                k++;
            }
        }
        if (sum != n) {
            cout << n << " is NOT perfect.\n";
        }
        else {
            cout << n << " = " << 1;
            for (int i = 1; i < k; i++)
            {
                cout << " + " << divisor[i];
            }
            cout << "\n";
        }
        k = 1;
        sum = 1;
    }
    return 0;
}

나는 배열로 구했지만, 크기를 정확히 알지 못하는 경우에는 '벡터'를 사용하는 것이 더 좋아보였다. 나는 벡터를 배운 적이 없어서 벡터에 대한 서술을 하도록 하겠다.

 

- VECTOR

c++ vector를 생성하면 메모리 heap에 할당된다.

int* a = new int[100];

배열을 동적했던 것이 기억난다면, 이와 마찬가지로 heap에 할당되는 것이다. 속도적인 측면에서는 array에 비해 성능이 떨어지지만, 메모리를 효율적으로 관리할 수 있다. #include <vector>을 해야 하는 것을 잊지말자!

vector<자료형> 변수명;
vector<int> v1;
vector<double> v2 (5); // 크기가 5인 벡터 생성 후 0으로 초기화 
vector<int> v3 = {1, 2, 3, 4, 5}; // 오른쪽 변수값으로 초기화

벡터 할당은 이와 같이 이루어진다. 

v.begin(); // 벡터의 시작 주소
v.end(); // 끝부분 + 1 주소
v.at[i]; // i번째 값, 요소 밖으로 접근하면 오류
v[i]; // i번째 값, 효율적인 측면에서 이걸 사용

벡터의 주소값과 인덱스에 접근하는 방법이다. 배열과 거의 비슷하다.

v.push_back(10); // 마지막에 10 넣기
v.pop_back(); // 마지막 제거
v.insert(삽입주소, 변수값);
v.inset(v.begin() + 1, 100);
v.clear(); // 벡터 모든 요소 지우기
v.resize(원하는벡터사이즈); // 사이즈 변경
v.swap(벡터변수); // 벡터와 벡터 swap

기본적인 벡터 함수들이다. push_back() 함수의 경우 또는 insert를 하는 경우는 모든 값을 새로운 메모리에 복사 한 후 해당 자리에 값을 넣게 된다. (마치 배열에 insert 할때 구현하는 것처럼)

v.size(); // 벡터 크기

벡터의 크기는 size로 반환받을 수 있다.

벡터 관련 함수는 더 있지만 현재 문제에서는 이정도까지만 하도록 하겠다.

 

#include<iostream>
#include<vector>
using namespace std;
int main() {
    ios::sync_with_stdio;
    cin.tie(0);
    vector<int>divisor;
    int n, sum = 0;
    while (1) {
        cin >> n;
        if (n == -1)
            break;
        for (int i = 1; i < n; i++)
        {
            if (n % i == 0) {
                divisor.push_back(i);
                sum += i;
            }
        }
        if (sum != n) {
            cout << n << " is NOT perfect.\n";
        }
        else {
            cout << n << " = " << 1;
            for (int i = 1; i < divisor.size(); i++)
            {
                cout << " + " << divisor[i];
            }
            cout << "\n";
        }
        sum = 0;
        divisor.clear();
    }
    return 0;
}

벡터로 다시 구현을 해봤다.

메모리 측면에서 vector을 사용하는 것이 더 효율적이었다.

 

 

 

1978. 자연수 M과 N이 주어질 때 M이상 N이하의 자연수 중 소수인 것을 모두 골라 이들 소수의 합과 최솟값을 찾는 프로그램을 작성하시오.

#include<iostream>
#include<vector>
using namespace std;
int main() {
    ios::sync_with_stdio;
    cin.tie(0);
    int n, count = 1, prime = 0;
    cin >> n;
    vector<int>divisor(n);
    for (int i = 0; i < n; i++)
    {
        cin >> divisor[i];
        for (int j = 1; j < divisor[i]; j++)
        {
            if (divisor[i] % j == 0) {
                count++;
            }
        }
        if (count == 2)
        {
            prime++;
        }
        count = 1;
    }
    cout << prime;
    return 0;
}

알다시피 벡트를 사용하지 않고 변수로 해도 전혀 상관없는 문제이다. 위에서 벡터를 공부해봤기 때문에 한번 써봤다. 그거 외에는 전혀 쓸 이유가 없다. 나는 최대한 for문을 덜 반복하는 걸 좋아하는데, 자연수들은 무조건 자기자신을 약수로 갖는다. 그렇기 때문에 굳이 자기 자신과 자기 자신을 나눠서 0인지 확인하는 일을 할 필요가 없다. 그래서 count가 항상 1로 설정되어 있는 것이다. 여기서는 소수이므로 1을 나누는 번거로운 행동을 하지만, 다른 코드에서는 j가 항상 2로 시작한다.

 

 

 

2581. 자연수 M과 N이 주어질 때 M이상 N이하의 자연수 중 소수인 것을 모두 골라 이들 소수의 합과 최솟값을 찾는 프로그램을 작성하시오.

#include<iostream>
#include<vector>
using namespace std;
int main() {
    int m, n, count = 1, prime = 0;
    cin >> m >> n;
    vector <int> v;

    while (m <= n) {
        for (int i = 1; i < m; i++)
        {
            if (m % i == 0) {
                count++;
                if (count > 2)
                    break;
            }
        }
        if (count == 2) {
            prime += m;
            v.push_back(m);
        }
        count = 1;
        m++;
    }
    if (v.size() == 0)
        cout << -1;
    else
        cout << prime << "\n" << v[0];
    return 0;
}

여기서 또 벡터를 사용했지만, min이라는 변수를 만들고 -1로 설정한 다음에 if (count == 2) 안에 min이 -1이라면 min 값을 업데이트 해주는 방식으로 해줘도 된다. 그리고 약수를 3개 이상 찾은 경우는 굳이 다른 약수가 있는지 확인할 이유가 전혀 없다. 그렇기 때문에 count가 2를 넘는 순간 break 해서 소수가 아니라고 판단하면 충분하다.

 

 

 

11653. 정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오.

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main() {
    // 소인수분해 : 소수로 이루어진 값들로 표현하는것
    int n, count = 1;
    cin >> n;
    
    vector <int> prime;
    for (int i = 2; i <= n; i++)
    {
        for (int j = 1; j < i; j++)
        {
            if (i % j == 0)
                count++;
            if (count > 2)
                break;
        }
        if (count == 2)
            prime.push_back(i);
        count = 1;
    }
    vector <int> prime_n;
    while (n != 1) {
        for (int i = 0; i < prime.size(); i++)
        {
            if (n % prime[i] == 0) {
                prime_n.push_back(prime[i]);
                n /= prime[i];
                break;
            }
        }
    }
    sort(prime_n.begin(), prime_n.end());
    for (int i = 0; i < prime_n.size(); i++)
    {
        cout << prime_n[i] << '\n';
    }
    return 0;
}

시간 초과가 발생했다. 나는 n 미만의 소수를 모두 구해서 계산하는 코드를 짰는데, 사실 그럴 필요가 전혀 없는 문제이다.

 

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main() {
    // 소인수분해 : 소수로 이루어진 값들로 표현하는것
    int n, count = 1, i = 2;
    cin >> n;
    vector <int> prime_n;
    while (n != 1) {
        if (n % i == 0) {
            prime_n.push_back(i);
            n /= i;
        }
        else {
            i++;
        }
    }
    for (int i = 0; i < prime_n.size(); i++)
    {
        cout << prime_n[i] << '\n';
    }
    return 0;
}

소수를 구함과 동시에 그 소수가 n을 나눌 수 있는 값인지 확인하는 것이다. 나는 밑에서 for문을 돌렸는데, 벡터 사용하지 않고 if (n%i==0) 안에 i를 출력하는 것을 넣으면 된다. 저장할 필요가 없다.