TIL 23-05-07 유클리드 호제법

1. 백준 알고리즘 - 최소공배수

 문제점

https://www.acmicpc.net/problem/1934

1934번: 최소공배수

 시도해 본 것들

최대 공약수, 최소공배수 구하기

def divisors(num):
    num_list = []
    while num != 1:
    # continue를 한다고 for문이 2로 초기화가 안됨
        for n in range(2, num+1):
            if num % n == 0:
                num //= n
                num_list.append(n)
                continue
    return num_list


def answer(A, B):
    # set으로 날리면 2*2*2같은 경우 안됨
    AB = set(A+B)
    my_answer = 1
    for num in AB:
        my_answer *= num
    return my_answer


for _ in range(int(input())):
    A, B = map(int, input().split())
    print(answer(divisors(A), divisors(B)))

divisors를 통해서 공약수들 구하기

answer로 최소공배수 구하기

 

divisors 수정

n = 2
    while num != 1:
        # for n in range(2, num+1):
        if num % n == 0:
            print(num, n)
            num //= n
            num_list.append(n)
            continue
        n += 1
    return num_list

continue를 통해서 if문에 진입하면 n을 2로 초기화 하기  

공약수들은 나왔지만, 이것을 최대공약수로 만들고 활용해서 최대 공배수로 만드는 방법을 모름

 

구글링을 통해서 유클리드 호제법 찾기

1071과 1029의 최대공약수를 구하면,

1071은 1029로 나누어 떨어지지 않기 때문에, 1071을 1029로 나눈 나머지를 구한다. ≫ 42
1029는 42로 나누어 떨어지지 않기 때문에, 1029를 42로 나눈 나머지를 구한다. ≫ 21
42는 21로 나누어 떨어진다.
따라서, 최대공약수는 21이다.

 A % B != 0이면 A % B를 구하고,

B % (A%B)를 시도하고

(A%B) % (B%(A%B)를 시도한다.  

 

유클리드 호제법 구현 시도

def euclidean_algorithm(A, B):
    # 무조건 A가 큰값 고정
    if A < B:
        A, B = B, A
    while True:
        if A % B == 0:
            gcd = B
            return gcd
        else:
            B = A % B

유클리드 호제법을 제대로 이해하지 못해서 else문에서 A를 수정하거나 gcd를 사용해야했는데 이를 놓침

 

def gcd(A, B):
    # 무조건 A가 큰값 고정
    if A < B:
        A, B = B, A
    C = A % B
    if A % B == 0:
        gcd = B
    else:
        while B % C != 0:
            C = B % C
            gcd = C
        # 최대 공약수
        # greatest common divisor
    return gcd

gcd 설정값 문제 있음  

 

포기전 마지막 코드 

def get_gcd(A, B):
    # 무조건 A가 큰값 고정
    if A < B:
        A, B = B, A
    if A % B == 0:
        gcd = B
    else:
        gcd = A % B
        while B % gcd != 0:
            gcd = B % gcd
        # 최대 공약수
        # greatest common divisor
    return gcd

여기까지 시도 후 시간을 너무많이 쓰고 더 이상 생각이 떠오르지 않아서 TIL 작성 시작 

TIL 작성 중 유클리드 호제법을 다시 정리하는 과정에서 내가 작성한 코드와 맞지 않는 느낌 발생 

그래서 정리한 예시를 바탕으로 get_gcd 수정

 

수정 된 gcd

def get_gcd(A, B):
    # 무조건 A가 큰값 고정
    if A < B:
        A, B = B, A
    # B가 최대 공약수인 경우 
    if A % B == 0:
        return B
    else:
        gcd = A % B
        # B % (A%B)
        while B % gcd != 0:
        # (A%B) % (B%(A%B)구현
            B, gcd = gcd, B % gcd
    return gcd

B = (A%B)를 제대로 반영하지 못해서 발생한 문제였음을 완성된 코드를 보고 알 수 있었다. 

 해결 방법

def get_gcd(A, B):
    # 무조건 A가 큰값 고정
    if A < B:
        A, B = B, A
    # A % B != 0 판단하기 
    if A % B == 0:
        return B
    else:
        gcd = A % B
        # (A%B) % (B%(A%B) if B % gcd != 0 else B % (A%B)
        while B % gcd != 0:
        # (A%B) % (B%(A%B)구현
            B, gcd = gcd, B % gcd
    return gcd

for _ in range(int(input())):
    A, B = map(int, input().split())
    print(A*B//get_gcd(A, B))

 

 알게 된 점

수식으로 옮기는 과정에서 벌써 이런 시행착오를 겪는 것을 보면서 하루만에 수식 자체에 대한 이해도의 중요성을 깨닫는다. 

소소하지만 가끔 보던 gcd가 최대 공약수를 뜻하는 것을 알 수 있었다. 

제대로 구현한 것 같지만, 문제가 발생할 때는 내가 제대로 수식을 이해하고 구현했는지 다시 확인하자.