[01-1] 최대공약수 찾기

1. 알고리즘

최대공약수를 찾기 위해 유클리드 알고리즘을 사용합니다. "C로 배우는 알고리즘"에서 유클리드의 알고리즘을 말로 표현하면 다음과 같다고 합니다. (내용을 조금 바꿨습니다. 인터넷에서 찾은 링크를 참고해도 좋겠습니다.)

1. 두 정수 u와 v를 입력 받는다.

2. v가 u보다 크다면, v와 u의 값을 교환한다.

3. u-v를 u에 저장한다.

4. u가 0인가? 아니면 2로 돌아간다. u가 0이면 v가 최대 공약수이다.

2. 동작 코드

아래와 같이 Python으로 작성했습니다.

# Minus methods
def get_gcd(u, v):
    while u != 0:
        if u < v:
            t = u
            u = v
            v = t
        u = u - v
    return v

단순히 C를 Python으로 옮긴 것입니다.

뺄셈으로는 속도가 느려서, modulus 연산자를 이용해서 속도를 개선합니다.

# Modulus methods
def gcd_modulus(u, v):
    while v != 0:
        t = u % v
        u = v
        v = t
    return u

재귀호출을 이용한 코드는 아래와 같습니다.

# Recursion methods
def gcd_recursion(u, v):
    if v == 0:
        return u
    else:
        return gcd_recursion(v, u % v)

3. 실행 코드

두 수를 입력 받아서 위의 함수들을 호출하는 실행 코드는 다음과 같이 작성했습니다. ("C로 배우는 알고리즘" 리스트 1-3 : EUCLID2.C에 대응)

# Main function
LOOP = 10000

print("Input 0 to end program")

while True:
    print()
    first_input = int(input("Input first integer : "))
    second_input = int(input("Input second integer : "))

    if first_input < 0 or second_input < 0:
        print("Please input positive integer")

    if first_input == 0 or second_input == 0:
        print("End of program")
        break

    start_time = time.process_time()
    for i in range(0, LOOP):
        gcd = get_gcd(first_input, second_input)
    end_time = time.process_time()
    print("Minus methods : GCD of", first_input, "and", second_input, "is", gcd, "in", end_time-start_time)

    start_time = time.process_time()
    for i in range(0, LOOP):
        gcd = gcd_modulus(first_input, second_input)
    end_time = time.process_time()
    print("Modulus methods : GCD of", first_input, "and", second_input, "is", gcd, "in", end_time-start_time)

    start_time = time.process_time()
    for i in range(0, LOOP):
        gcd = gcd_recursion(first_input, second_input)
    end_time = time.process_time()
    print("Recursion methods : GCD of", first_input, "and", second_input, "is", gcd, "in", end_time-start_time)

4. Tips

1. Python에서 사용자에게 입력을 받기 위해서 input()을 사용했으며, input()은 'str'을 입력 받기 때문에 int()를 이용해서 integer로 변환했습니다.

2. 시간 측정을 위해서는 Python의 time 모듈에서 process_time()을 사용하였습니다.

5. 코드

https://github.com/steady08/python_beginner_algorithm/blob/master/Chapter_01/Ch_01_1.py