파이썬 알고리즘: 유클리드 호제법으로 최대공약수 최소공배수 구하기

알고 넘어가야 할 이론:

최대공약수 구하는 방법 + 유클리드 호제법:

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

---

오늘 공부한 내용

문제:

두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.

 

제한 사항

• 두 수는 1이상 1000000이하의 자연수입니다.

입출력 예

nmreturn

3	12	[3, 12]
2	5	[1, 10]

입출력 예 설명

입출력 예 #1
위의 설명과 같습니다.

입출력 예 #2
자연수 2와 5의 최대공약수는 1, 최소공배수는 10이므로 [1, 10]을 리턴해야 합니다.

내가 생각한 문제풀이 : 

먼저 초등학교때 배운 기억을 되짚어서 최소공배수와 최대공약수를 구하는 방법을 생각해했다.

이렇게 푸는 방법을 코드로 어떻게 구현할까 고민을 하다가 

두 수가 딱 떨어지게 나누어지는 규칙성을 발견했다. 

그래서 이것을 코드로 옮기면 n % a == 0 and m % a == 0 라고 조건을 생각해낼 수 있었다.

for 문으로 1부터 커지게 하는데, 조건에 맞을때까지 계속 같은 수를 나눠줄 순 없을까? 고민을 하다가

while문을 사용하기로 했다.

그런데 while문을 사용하면 무한루프가 돌 수 있기 때문에 주의해야 한다.

1을 계속 나누게 되면 무한루프에 빠지는 문제가 발생한다. 따라서 a>1 라는 조건을 추가해주었다.

 최대 공약수의 경우 배열에 나누어지는 수를 넣어두고, 마지막에 배열을 for문 돌면서 곱해주면 될 것 같았다.

이 생각을 코드로 옮기면

 

def solution(n, m):
    answer = []
    max = []
    min = 1
    max2 = 1
    print("-----------처음 시작---------------")
    print(f'max: {max}')
    print(f'n : {n} , m: {m}')
    for a in range(1,n+1):
        while a>1 and n % a == 0 and m % a == 0:
            max.append(a)
            n = n//a
            m = m//a
            print(f'-----------와일문{a}---------------')
            print(f'max: {max}')
            print(f'n : {n} , m: {m}')
            if a == n:
                break
    print("-----------포문 끝---------------")
    print(f'max: {max}')
    print(f'n : {n} , m: {m}')

    for x in max:
        max2 = max2*x
        print(f'max2 : {max2}')
    min = max2*m*n
    print(f'min : {min}')
    answer.append(max2)
    answer.append(min)
    return answer

print(solution(6, 12))

 이렇게 옮길 수 있다. 

계속해서 값을 확인하기 위해 print 구문을 넣어  단계별로 계산한 값을 보기 편하게 해주었다.

 

결과값이 잘 나온다.

 

 

유클리드 호제법을 활용한 코드:

def solution(a, b):
    c, d = max(a, b), min(a, b)
    t = 1
    while t > 0:
        t = c % d
        c = d
        d = t
    # 최소 공배수 구하는 공식
    answer = [c, int(a*b/c)]

    return answer

print(solution(6, 12))

유클리드 호제법을 활용한 풀이방법이다.

 

코드분석 :

 

최소 공배수 구하는 공식 = 두 자연수 a와 b를 곱한것을 최대공약수 c로 나눈다. 

 

---

느낌점

초등학교때 유클리도 호제법을 알았으면.. 내가 수학을 포기하진 않았을텐데.. 

최대공약수를 이렇게 쉽게 구하는 방법이 있었다니...