20230815_TIL_프로그래머스{유클리드 호제법 : 최대공약수}

오늘의 한 줄 TIL : 두 수의 최대 공약수를 유클리드 호제법을 배웠다.

---

유클리드 호제법이란?

- 호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘을 나타낸다

- 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라,나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수

 

빠르게 코드로 알아보자 

def gcd(a, b):
    while b > 0:
        a, b = b, a % b
    return a

위에서 언급한 순서대로 while 문에서 b가 0보다 큰 조건문을 걸어주어 b가 0이 되는 순간 while 문이 정지된다.

(내가 참고한 블로그는 a와 b의 크기는 상관 안한듯 하지만 위키백과에 의하면 해야하는 건지 의문이다)

계속 반복하여 a%b가 0이 되는 순간 a와 b의 최대 공약수를 구할 수 있다.

---

알고리즘이 사용된 문제 (프로그래머스 - 유한 소수 판별하기)

 

해당 문제를 요약하자면 

1. 분자가 a  / 분모가 b로 주어진다. (즉, a/b)

2. 해당 분수를 기약분수로 나타낸 후

3. 분모의 소인수가 2와 5만 있다면 해당 분수는 유한소수이다.

4. 유한소수는 1, 그렇지 않은 무한 소수는 2로 return 하라.

 

해당 문제에서 hint로 최대공약수로 약분하면 기약분수가 된다는 것을 알려주었다.

 

코드

def gcd(a, b):
    while b > 0:
        a, b = b, a % b
    return a

def solution(a, b):
    answer = 0
    ## 정수로 나눠지는 경우도 유한소수로 분류
    if a%b == 0:
        return 1
        
    ## 분모의 소인수만 알면 되기에 분모만 약분을 진행
    b = b//gcd(a,b) # 분모 // 최대공약수
    
    ## 분모 이하의 소수 구하기
    decimal = []
    for num in range(2,b+1):
        cnt = 0
        for i in range(2,int(num**0.5)+1):
            if num % i == 0:
                cnt += 1
        if cnt == 0:
            decimal.append(num)

    ## 해당 소수가 인수인지 판별
    factor = []
    for dec in decimal:
        if b%dec == 0:
            factor.append(dec)
    
    # 정렬해줘서 빠르게 비교하기 위함
    factor.sort()
    if (factor == [2,5]) or (factor == [2]) or (factor == [5]):
        answer = 1
    else:
        answer = 2 
    
        
    return answer

---

 

refernce site

1. 유클리드 호제법 코드 참조 블로그

2. 유클리드 호제법 위키백과

3. 프로그래머스 문제 - 유한소수 판별하기