안타깝게도 호재가 아니라 호제였다.

국장에 호재가 올까요?


일단 오늘은 아니다.

유클리드 호제법

두 정수의 최대 공약수 구하는 알고리즘이란다.

기원전 3세기 사람이 알고리즘을 만들었다는게 다소 충격적이다.

그 때에도 컴퓨터가 있었다니…

컴퓨터는 고구려에서 개발했다는 사실은
수박도에도 나와있는데 아무래도 그리스가 원조였나 보다.

스타는 사실 고전게임이 아닐지도 모르겠다.

기본 원리

유클리드 호제법은

두 정수를 직사각형의 변이라 생각하고 진행한다.

그리고 이 직사각형을 정사각형으로 나누어가는 방식으로 진행하고 말이다.

가능한 큰 정사각형으로 나누면 크기에 안맞는 직사각형이 나오고

이를 다시 쪼개길 반복해가며 전부 정사각형으로 나눠질때까지 진행한다.


존나 힙한거 같다. 유클리드

파이썬 예시

내가 만든 건 아니고 교재에 적혀있는 코드다.

# 유클리드 호제법

def gcd(x: int, y: int) -> int:
    """정수값 x와 y의 최대 공약수를 반환"""
    if y == 0:                # 전부 정사각형이 되어버림
        return x
    else:
        return gcd(y, x % y)  # 정사각형이 될때까지 쪼개기

if __name__ == '__main__':
    print('두 정숫값의 최대 공약수를 구합니다.')
    x = int(input('첫번째 정숫값 : '))
    y = int(input('두번째 정숫값 : '))

    print(f'최대 공약수는 : {gcd(x, y)}')

※ math 모듈에서 gcd() 함수 제공하니 실전에선 이거 쓰자

그때에도 VS로 코딩했을지 궁금하다.

아무래도 영어 대신 라틴어를 썼을테니 코딩하기 더 힘들었을 듯 하고 말이다.

라틴어 코딩은 존나 힙 하긴 하다.