문제

프로그래머스 연습 문제

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

나의 답안

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

• 최대공약수를 찾기 위해 n과 m 중 작은 값부터 1까지 내려가면서 반복했다.
  range(start, stop, step) 중 step 부분을 음수로 작성하면, 범위가 내림차순으로 생성된다.

• if 문으로 n과 m이 동시에 나눠지는 숫자 i를 찾아 공약수를 구한다. 이때 range의 범위가 내림차순이니까 가장 처음에 나오는 i가 최대공약수이다.
  이 값을 찾아 변수 a 에 담고, break 문을 사용하여 반복문을 종료하도록 했다.

• break 문을 작성하지 않으면 가장 마지막에 나오는 i값인 1이 a에 저장된다.

• 이후 최소공배수를 찾기 위해 n과 m 중 큰 값부터 n * m 까지의 수를 range의 범위로 잡는다.

• if 문으로 n과 m의 배수인 j를 찾는다.
  마찬가지로 가장 처음에 나오는 j가 최소공배수이므로 변수 b 에 j를 저장하고 반복문을 종료한다.

• 최대공약수 a와 최소공배수 b를 리스트에 담아 return 한다.

---

다른 사람의 풀이

유클리드 호제법

자연수 2개의 최대공약수를 구하는 알고리즘

    GCD(n,m) = GCD(m,n%m)
    n%m이 0이 될 때까지 반복, 최종적으로 나온 m이 최대공약수
    
    e.g.) 12와 16의 최대공약수 구하는 법
    GCD(12, 16) = GCD(16, 12 % 16) = GCD(16, 12)
    GCD(16, 12) = GCD(12, 16 % 12) = GCD(12, 4)
    GCD(12, 4) = GCD(4, 12 % 4)
    =GCD(4, 0)

---

파이썬 코드로 구현하기

def gcd(n, m):
    if m == 0:
        return n
    else:
        return gcd(m, n % m)

최소공배수 구하기

n = GCD(n,m) * 몫1
m = GCD(n,m) * 몫2
LCM(n,m) = GCD(n,m) * 몫1 * 몫2
LCM(n,m) = n * m / GCD(n,m)

def lcm(n, m):  
    return n // gcd(n, m) * m

---

유클리드 호제법을 이용한 풀이 1

def gcd(a, b):
    return b if a % b == 0 else gcd(b, a % b)

def lcm(a, b):
    return int(a * b / gcd(a, b))


def gcdlcm(a, b):
    answer = [gcd(a,b), lcm(a,b)]

    return answer

• 람다 사용해서 구현하기

def solution(n, m):
    gcd = lambda a,b : b if not a%b else gcd(b, a%b)
    lcm = lambda a,b : a*b//gcd(a,b)
    return [gcd(n, m), lcm(n, m)]

GCD와 LCM에 대한 함수를 정의해서 풀이했다.

유클리드 호제법을 이용한 풀이 2

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

• a와 b 중 큰 수를 변수 c에 저장,
  a와 b 중 작은 수를 변수 d에 저장했다.
  이런 방법을 tuple unpacking이라고 한다.
  tuple unpacking : 여러 개의 변수에 동시에 값을 할당하는 방법

• 변수 t를 생성하여 c를 d로 나눈 나머지를 t에 저장한다.
  tuple unpacking 방식을 사용하여 변수 c에 d의 값을 할당하고 d에는 t의 값을 할당한다.
  이 과정을 t가 0이 될 때까지 반복한다. (while t > 0)
  최종적으로 c에 저장된 값이 최대공약수가 된다.

• 최소공배수는 a와 b의 곱을 최대공약수 c로 나누어 계산한다.

---

다른 풀이

def gcdlcm(a, b):
    for i in range(a):
        if a%(a-i)+b%(a-i) == 0:
            return [a-i, a*b/(a-i)]

• a를 (a-i)로 나눈 나머지와 b를 (a-i)로 나눈 나머지의 합이 0이 되는 경우,
  (a-i)가 a와 b의 최대공약수이다.

• a*b/(a-i)를 계산하여 a와 b의 최소공배수를 구한다.