알고리즘(1)

프로그래머스 lv1 문제를 풀던 중.. 두 수의 최대공약수와 최소공배수를 찾는 문제를 풀었다.

두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성하는 문제이다.

내가 작성한 코드는 다음과 같다.

  def solution(n, m):
      arr = []
      if m % n == 0:
          arr.append(n)
          arr.append(m)
      else:
          for i in range(n-1,0,-1):
              if (n%i ==0) and (m%i == 0):
                  arr.append(i)
                  arr.append((n/i)*(m/i)*i)
                  break
      return arr

나의 풀이 (기본에 충실한 방법)

처음에는 나름 기본(?)에 충실하게 접근하려고 애썼다.
반복문을 돌면서 일일이 나머지가 0이 되는 수를 찾는 방식이다. 일단 정답은 맞췄지만, 다른 사람들의 풀이를 보니 훨씬 효율적이고 수학적인 접근법이 있었다. 바로 '유클리드 호제법' 이다!

💡 새로운 발견: 유클리드 호제법이란?

유클리드 호제법 : 두 양의 정수 혹은 두 다항식의 최대공약수를 구하는 알고리즘으로, 정수론을 배우게 된다면 가장 먼저 배우는 공식이며 인류 최초의 알고리즘이라고 한다!

알고리즘 동작 단계

1. 두 수 중 큰 수를 작은 수로 나눈다.
2. 나머지가 0이면 작은 수가 최대 공약수가 된다.
3. 나머지가 0이 아니면 작은 수가 큰 수가 되고, 나머지를 작은 수로 대체하고 1단계로 돌아간다.

💻 코드로 구현해보기
천천히 생각해보자.
두 수 중 큰 수를 작은 수로 나눠야 하므로 max와 min 함수로 두 수를 정렬해주면 편하다.
나머지가 0이 될 때까지 이 과정을 반복해야 하므로 while문을 사용하는 것이 적절해 보인다.

1. 최대공약수 (GCD) 구하기

  def gcd(a,b):
    a,b = max(a,b), min(a,b)

    while b:
      a, b = b, a%b
    return a

2. 최소공배수 (LCM) 구하기
   최대공약수를 구했다면 최소공배수는 아주 쉽게 구할 수 있다.
   두 수의 곱 = 최대공약수 * 최소공배수 라는 공식이 성립하기 때문이다.

def gcd(a,b):
  a,b = max(a,b), min(a,b)
  c = a*b
  
  while b:
    a, b = b, a%b
  return a, c//a

🎁 Feat. 파이썬 math 라이브러리

유클리드 호제법을 직접 구현해보는 것도 아주 훌륭한 공부지만, 실무나 코딩 테스트에서 시간을 단축해야 할 때는 파이썬의 강력한 내장 라이브러리를 사용할 수 있다.

파이썬 math 라이브러리에는 이미 gcd와 lcm 함수가 내장되어 있어서, 단 한 줄만으로 값을 구할 수 있다!

import math

def solution(n, m):
    return [math.gcd(n, m), math.lcm(n, m)]

이번 문제를 통해 수학적 지식이 알고리즘의 효율성을 얼마나 높여줄 수 있는지 깨달았다. 앞으로도 단순히 풀고 넘어가는 것이 아니라, 더 나은 방법이 있는지 꼭 확인하는 습관을 들여야겠다.