Level 0. 소인수분해

Level 0. 소인수분해

 

 

소인수분해는 다음과 같은 과정을 통해 수행할 수 있다.

 

n = 120을 예로 들 때

1. i는 2부터 시작한다.
2. n이 1이 아닌 동안 반복한다.
3. 1씩 증가시키며 나누어 떨어지는 수 i를 찾는다.
4. i를 소인수 리스트에 추가한다.
5. n이 더 이상 나누어 떨어지지 않을 때까지 i로 나눈다.
6. 2로 돌아가 과정을 반복한다.

 

 

아래는 재귀를 이용하여 부문제로 나누어 해결한 풀이이다.

 

예들 들면

• solution(120)은 2와 solution(60)의 결과를 합친 것이다.
• solution(60)은 2와 solution(30)의 결과를 합친 것이다.
• solution(30)은 2와 solution(15)의 결과를 합친 것이다.
• solution(15)는 3과 solution(5)의 결과를 합친 것이다.
• solution(15)는 3와 solution(5)의 결과를 합친 것이다.
• solution(5)는 5이다.

 

중복 원소 제거와 정렬을 위해 set을 사용하였으나 마지막 풀이에서 중복 원소를 제거할 필요 없이 좀 더 최적화하는 방법이 나와있다.

 

참고했던 자료에서는 i를 추가할 때도 solution(i)와 같이 소인수분해하여 추가했는데 그럴 필요는 없다.

• i가 작은 수부터 시작하기 때문에 나누어 떨어지는 수 i는 항상 소수이다.
• i = 2j라고 할 때, i가 나누어 떨어지는데 j를 확인하지 않았다는 건 말이 안 되기 때문이다.

 

#include <iostream>
#include <vector>
#include <set>

using namespace std;

vector<int> solution(int n)
{
    for (int i = 2; i < n; ++i)
    {
        if (n % i == 0)
        {
            set<int> st = {i};
            vector<int> v = solution(n / i);

            st.insert(v.begin(), v.end());

            return vector<int>(st.begin(), st.end());
        }
    }

    return vector<int>({n});
}

 

아래는 반복문을 통해 해결한 풀이이다.

• i < n이 아니라 1 < n이 종료 조건임에 주의해야 한다.

 

i가 나누어 떨어지는 수인 경우 i를 증가시키지 않고 계속 n을 나눈다.

 

마지막에 정렬 후 중복 원소를 제거하여 반환한다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> solution(int n)
{
    vector<int> answer;

    for (int i = 2; 1 < n;)
    {
        if (n % i == 0)
        {
            n /= i;
            answer.emplace_back(i);
        }
        else
        {
            ++i;
        }
    }

    sort(answer.begin(), answer.end());
    answer.erase(unique(answer.begin(), answer.end()), answer.end());

    return answer;
}

 

정렬과 중복 제거를 하지 않아도 되는 풀이이다.

 

나누어 떨어지는 수를 찾은 경우 그냥 그때 한 번에 다 나눠버리는 것이다.

 

i가 작은 수부터 시작하므로 정렬할 필요도 없고 1번만 삽입하므로 중복 제거도 불필요하다.

 

#include <iostream>
#include <vector>

using namespace std;

vector<int> solution(int n)
{
    vector<int> answer;

    for (int i = 2; 1 < n; ++i)
    {
        if (n % i == 0)
        {
            answer.emplace_back(i);

            do
                n /= i;
            while (n % i == 0);
        }
    }

    return answer;
}