[gcd, 최대공약수] 프로그래머스 lv 0. 유한소수 판별하기

문제

문제 바로가기

 

유클리드 호제법이란

정수 A와 B가 있다.
A * s + B * t = r

을 만족하는 정수 s와 t가 있다는 것을 전제로 최대공약수 r을 구한다.

128과 42를 예시로 식을 풀어보자면,
128_s + 42_t = 최대공약수 r
128 = 42 * 어떤 몫 + r
형식으로 표현하고, 42와 r을 계속해서 풀어나가다 보면 나머지가 0이 된다.
그 때 마지막으로 대입됐던 수(이전 식의 나머지였던 수)가 128과 42의 최대 공약수가 된다.

• 128과 54 예시
  128 = 54 * 2 + 20
  54 = 20 * 2 + 14
  20 = 14 * 1 + 6
  14 = 6 * 2 + 2
  6 = 2 * 3 + 0

따라서 2가 128과 54의 최대공약수이다.

gcd는 최대공약수를 구할 때 사용한다. 파이썬에 내장 라이브러리가 있다.

from math import gcd
최대공약수 = gcd(a, b)

개선한 풀이법

• 유클리드 호제법을 이용해 gdc를 직접 구현, (재귀)

def gcd(x,y):
    big,small = max(x,y), min(x,y)
    mok = big//small
    res = big%small
    if res != 0:
        return gcd(small, res)
    else:
        return small

def solution(a, b):
    gcd_num = gcd(a,b)

    if gcd_num != 1:
        b = b//gcd_num
    while b%2==0:
        b//=2
    while b%5==0:
        b//=5

    answer = 1 if b == 1 else 2
    return answer

참고할 풀이법

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

while 문이랑, 몫으로 나눈 값을 할당한 것 기억해야 함