[알고리즘 프로그래머스] 최대공약수와 최소공배수 (LEVEL 1)

(문제) 최대공약수와 최소공배수

---

두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요.

배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다.

예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.

입력설명

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

출력설명

두 수를 입력받아 두 수의 최대공약수와 최소공배수를 리스트로 반환하시오.

테스트케이스

입력예제	출력예제
3 12	[3,12]
2 5	[1, 10]

---

해결방법

방법 1

작은 정수 까지 반복문을 돌려서 입력으로 들어오는 두 값 모두 나누어 떨어지는 것이 존재하면 값을 저장한다.

그러면 마지막에 저장되는 값이 최대공약수가 된다.

최소 공배수는 입력으로 들어오는 두값을 곱한 값을 최대공약수로 나누면 나온다.

---

방법 2

유클리드 호제법

유클리드 호제법 설명 위키백과

**간단 설명 : **

입력으로 들어오는 두개의 수중에서 큰수에서 작은 수를 나눠서 나오는 나머지를 구한다.

작은 수와 구한 나머지를 나눠서 또 나오는 나머지를 구한다.

이 작업을 반복한다.

큰 % 작 = 나머지1
작 % 나머지1 = 나머지2
나머지1 % 나머지2 = 나머지3 ...

나머지가 없을 경우 나누는 값이 최대공약수가 된다.

최소공배수는 입력으로 들어오는 두개의 값을 곱한 값과 구한 최대 공약수 곱하기 최소공배수와 동일한 값을 가지게 된다.

동작 시각화

---

코드 방법1

n, m = map(int, input().split())

# 만약 공약수가 없으면 1이 초기값
answer = [1]

# 최대공약수
for i in range(1, n+1):
    if n % i == 0 and m % i == 0:
        answer[0] = i

# 최소공배수
answer.append(int(n*m/answer[0]))

print(answer)

코드 방법2 (유클리드 호제법)

n, m = map(int, input().split())

if n < m:
    n, m = m, n
    
save = n * m

# 나누어 떨어지지 않을 경우
# 나누어 떨어지지 않은 것과 더 작았던 것
while True:
    after_min = n % m
    
    # 나누어 떨어져서 최대 공약수
    if after_min == 0:
        break
    # 작았던 것이 큰것으로
    n = m
    # 나머지가 작은 것으로
    m = after_min

# 두 자연수의 곱 | 최소공배수 곱 최대공약수
return [m, int(save / m)]