'소인수분해'에 해당되는 글 1건

안녕하세요. 은공지능 공작소의 파이찬입니다.
오늘은 프로그래머스 유한소수 판별하기 문제 풀어보겠습니다.

문제를 풀기 위해 알아야 할 개념은 크게 2가지 입니다.
1. 유클리드 호제법 (최대공약수)
2. 소인수 분해

소인수 분해를 사용하지 않고 푸는 방법도 있는데,
가장 깔끔한 풀이법이었습니다.
해당 정답 공개 후, 문제 풀이 시작하겠습니다.

프로그래머스 문제 바로 가기 ↓↓↓ 링크 클릭

https://school.programmers.co.kr/learn/courses/30/lessons/120878

1. 정답 공개

from math import gcd
def solution(a, b):
    b //= gcd(a,b)
    while b%2==0:
        b//=2
    while b%5==0:
        b//=5
    return 1 if b==1 else 2

gcd는 최대공약수(Greatest Common Divisor, GCD)를 의미합니다.
파이썬의 math 라이브러리에 내장되어 있는 기본 함수를 사용했습니다.
(실제 코딩테스트에서 사용 가능 가능할지는 모르겠네요... 알아두면 개꿀이니 숙지는 해야겠습니다)

이후 분모(b)를 최대공약수로 나누고
각각 2와 5로 나누어 떨어진다면, while문에 진입합니다.
최종적으로 b가 1인지 아닌지를 return합니다.

소인수분해를 사용하지 않은 대신,
while문을 각각 사용한 것이 인상적이었습니다.

그러나 만약 math 함수를 쓰지 말라고 한다면?
면접에서 최대공약수 구하는 과정을 설명해보라 한다면?
왜 분모를 최대공약수로 나누는지 이유는?

그렇기 때문에 최대공약수를 구하는 유클리도 호제법과
소인수 분해에 대한 알고리즘을 꼭 아셔야 합니다!

2. 유클리드 호제법 (최대공약수 구하기)

간단한 문제를 통해 유클리드 호제법이 무엇인지 살펴보았습니다.
유클리드 호제법은 2가지만 기억하시면 됩니다.

① 다음 단계에서 분모는 분자가 된다.
② 다음 단계에서 나머지는 분모가 된다.
이제 유클리드 호제법을 코드로 구현해 보겠습니다.

def gcd(a, b):
    if a % b == 0:
        return b
    else:
        return gcd(b, a%b)

재귀함수를 이용하여 유클리드 호제법을 구현하였습니다.

① 다음 단계에서 분모는 분자가 된다. -> b가 a자리에 왔습니다.
② 다음 단계에서 나머지는 분모가 된다. -> a%b가 b자리에 왔습니다.

나머지가 0으로 나누어 떨어지면?
그것이 바로 최대공약수입니다.

3. 소인수 분해

def factorization(x):
    d = 2
    output = []
    
    while d <= x:
        if x % d == 0:
            output.append(d)
            x /= d
        else:
            d += 1
            
    return output

위의 코드는 소인수분해를 함수로 구현한 것입니다.
변수 d는 2부터 시작하여, 원래 input으로 주어진 x까지 반복됩니다.

그러나 x 또한 고정된 것이 아니라 변화합니다.
d로 나누어 떨어지면, 나누어 떨어진 몫을 x로 대체합니다. (x /= d)

마지막으로 반환되는 output은 소인수분해에 사용된
소수들을 담고 있습니다.

4. 유클리드 호제법 + 소인수분해를 이용한 풀이법

def gcd(a, b):
    if a % b == 0:
        return b
    else:
        return gcd(b, a%b)

def factorization(x):
    d = 2
    output = []
    
    while d <= x:
        if x % d == 0:
            output.append(d)
            x /= d
        else:
            d += 1
            
    return output
    
def solution(a, b):
    divide_num = gcd(b, a)
    result = b // divide_num
    
    for num in factorization(result):
        if num not in [2, 5]:
            return 2
    return 1

마지막 solution 파트에 대해서만 설명드리겠습니다.
최대 공약수를 구한 뒤, b를 최대공약수로 나누게 되면,
기약분수가 적용된 분모의 형태를 띄게 됩니다. (result)

그 이후는 문제에서 준 힌트와 동일합니다.
분모를 소인수 분해한 뒤, 2 또는 5 이외의 소인수가 나오는지 체크하는 과정입니다.
만약 하나라도 2 또는 5가 아니라면 무한 소수입니다.

for문에서 return되지 않고 끝까지 간다면?
유한소수이기 때문에 1을 return해주면 됩니다.

5. 마무리

개인적인 생각이지만,
이런 종류의 문제는 암기하고 많이 익숙해지는게 정답인 듯 합니다.
유클리드 호제법과 소인수분해를 알아야 수월하게 풀 수 있습니다.

어떻게 보면 마냥 모니터 앞에서 고민하는게 정답이 아닐 수도 있습니다.
사전 지식이 잘 탑재되어 있으면 쉽게 해결될 문제가 많습니다.
다만 차이가 있다면.. 힘들게 푼 문제가 기억에 오래 남는다 정도?
(그냥 여러 번 풀고 익히는게 더 기억에 오래 남을수도 있습니다)

그러니 알고리즘 문제를 풀다가 너무 답이 안나오면
해답을 보는 것도 괜찮은 방법입니다 :)
오늘은 이만 마치겠습니다. 수고하셨습니다.