최대공약수 tag - Voyager of Linux

분수 알고리즘에서 마지막으로 약분(reduce a Fraction to Lowest Terms) 을 합니다. 약분은 분자와 분모의 최대공약수(GCD, Great Common Divisor)로 나누는 것을 말합니다. 따라서 약분을 하기 위해서는 최대공약수를 구하면 됩니다. 약분, 최대공약수를 구하라. 최대공약수 구하기 1 최대공약수를 구하는 방법은 여러가지가 있는데 그 첫번째로 분자, 분모 두개를 동시에 나누었을때에 나머지가 없는 수를 구하면 됩니다. 1부터 시작해서 분자, 분모 두수중에 작은 수까지 대입해서 하나씩 나누어서 0이 되는지를 찾아보는 겁니다. 최대공약수를 구하는 무한대입법이라고 보시면 됩니다.

def GCDbyDivide(num1, num2):
    '''
        최대공약수를 구하는 알고리즘.
        두수를 나눗셈으로해서 가장큰 약수를 구하는 방법.
    '''
    if num1 < 0:
        raise RuntimeError('num1 must be above 0')
    if num2 < 0:
        raise RuntimeError('num2 must be above 0')
    
    miniNum = min(num1, num2)
    
    maxDiv = 1
    
    for i in range(1,miniNum+1):
        
        if num1%i == 0 and num2%i == 0:
            maxDiv = i
          
    return maxDiv

def GCDbyDivide(num1, num2):

'''

최대공약수를 구하는 알고리즘.

두수를 나눗셈으로해서 가장큰 약수를 구하는 방법.

'''

if num1 < 0:

raise RuntimeError('num1 must be above 0')

if num2 < 0:

raise RuntimeError('num2 must be above 0')

miniNum = min(num1, num2)

maxDiv = 1

for i in range(1,miniNum+1):

if num1%i == 0 and num2%i == 0:

maxDiv = i

return maxDiv

작은 수가 무엇인지를 구하기 위해서 min 함수를 이용했습니다. 무한대입법을 […]