유클리드 호제법

간단히 파이썬으로 다음과 같이 해결

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

 

완벽한 이해를 위해선 호제법이 동작하는 원리도 이해하면 좋겠지!

다음 유튜브 영상을 보면 쉽게 이해할 수 있다. 수악중독! 이분의 이름과 내이름이 같다. ㅎ

https://www.youtube.com/watch?v=J5Yl2kHPAY4 

 

백준 알고리즘에서 호제법은 필수인듯하다. 다른 방식으로 풀수 있지만, 시간제약으로 실패하는 경우가 있다.

간단한 알고리즘이므로 반드시 이해해 놓으면, 아주 많은 문제에서 활용할 수 있을 듯.

 

천천히 즐기며 하는 백준. 괜찮은 것 같다.

 

빨리 고수가 되어 [코딩 테스트] 준비 수업을 열어보고 싶다.

 

 

유클리드 호제법과 함께 소수 판별에 대한 부분도 쉽지만 정수론 관련해서 나올 수 있으니, 참고해서 기억해두자.

키포인트는 임의의 주어진 값 x에 대해서 소수 판별할때, 2부터 x-1까지의 값으로 나눈 값 중 0이 있으면 소수가 아니라는 것은 기본인데, 수행 시간을 압축하기 위해서 체크하는 수의 범위를 2부터 sqrt(x)+1 로 잡아 반복의 수를 크게 줄여야 수행 시간을 줄일 수 있다는 것이다. 

def isprime(x):
    if x == 0 or x == 1:
        return False
    for i in range(2, int(x**0.5)+1):
        if x % i == 0:
            return False
    return True