[프로그래머스_Lv1] 최대공약수와 최소공배수

최대공약수와 최소공배수

문제 링크

- 나의 풀이

def solution(n, m):
    answer = []
    for i in range(min(n, m), 0, -1):
        if n % i == 0 and m % i == 0:
            print(i)
            break
    for j in range(max(n, m), (n * m) + 1):
        if j % n == 0 and j % m == 0:
            print(j)
            break
    answer = [i, j]
    return answer

• 최대공약수 : 자연수 n, m중 작은 수 부터 1까지 1씩 감소하는 범위를 갖는 for 반복문을 진행하였고, 자연수 n, m 모두 i로 나누었을때 나머지가 0이 될때의 i 값이 최대공약수이다.
• 최소공배수 : 자연수 n, m중 큰 수부터 n*m 값까지의 범위를 갖는 for 반복문을 진행하였고, 자연수 n, m 각각을 j로 나누었을때 나머지가 0이 될때의 j 값이 최소공배수이다.
• i(최대공약수), j(최소공배수) 값을 answer 변수에 할당하여 return!

- 다른사람의 풀이

def gcdlcm(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

• 유클리드 호제법으로 풀이한 코드이다. max, min함수를 이용하여 변수를 재할당하였고 while 반복문을 이용하여 비교적 간단하게 유클리드 호제법을 표현한 것을 볼 수 있다. 유클리드 호제법에 대한 간략한 설명은 아래와 같다.

유클리드 호제법

• 유클리드 호제법(-互除法, Euclidean algorithm) 또는 유클리드 알고리즘은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘을 나타낸다.
  (출처 : 위키백과)

• 코드 작성을 위해 좀 더 쉽게 설명하자면,
  자연수 a를 b로 나눈 나머지와 b의 최대공약수는 a, b의 최대공약수와 같다는 원리가 핵심이다. 따라서 나눗셈만 반복하여 최대공약수 값을 구할 수 있다.

• 자연수 a, b가 주어졌을때, a를 b로 나누어 나머지를 구한다. 그리고 b를 a위치에, a%b(a를 b로 나눈 나머지 값) 값을 b위치에 할당하여 b값이 0이 될 때까지 반복한다.
  이를 코드로 작성하면 아래와 같다.

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