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

문제 보러가기


코드 및 풀이

def gcdlcm(a, b):
    max_num = max(a, b)
    min_num = min(a, b)
    while min_num != 0:
        max_num, min_num = min_num, (max_num % min_num)
    gcd_result = max_num
    lcm_result = (a * b) // max_num 
    return [gcd_result, lcm_result]

최대공약수(Greatest Common Divisor, GCD)는 주어진 수들의 공통적인 약수 중 가장 큰 값이다. 즉, 3과 12가 있을 때 두 수의 최대공약수는 3이다.

유클리드 호제법을 사용하여 풀었는데, 유클리드 호제법이란 2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란 두 수가 서로 상대방의 수를 나누어 결국 원하는 수를 얻는 알고리즘을 뜻한다.(더 알아보기)

위의 알고리즘을 이용하면 일단 나누어질 수가 나눌 수보다 커야하므로 두 수의 대소비교를 통하여 각각 max_num, min_num이라 정의하였다.

그리고 나누어보면 다음과 같은 규칙이 보인다.

(max_num, min_num)   # 주어진 값
(min_num, max_num % min_num)   # 몫을 다시 나머지로 나눈다   
(max_num % min_num, min_num // (max_num % min_num))

...

a, b = b, a % b   # 일반화

위의 규칙을 가지고 나머지가 0이 될 때까지 계산을 반복하여 나왔을 때 나누어지는 값(=이전 식에서의 나누는 값)이 최대공약수이다.

최소공배수(Least Common Multiple)는 주어진 두 수 모두의 배수를 만족하는 가장 작은 수이다. 최소공배수는 두 수의 곱을 최대공약수로 나눈 값이므로 최대공약수를 먼저 구한 뒤 초기값의 곱을 구해 나누어주면 된다.


+추가

위 최대공약수를 구할 때 사용한 코드는 메모이제이션 개념을 활용한 것이다.


메모이제이션, Memoization

컴퓨터 프로그램이 동일한 계산을 반복할 때 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다.

단어를 봐도 메모하다의 의미를 가지고 있는 memo의 의미가 있으며, 메모이제이션의 의미는 메모리에 넣다라는 의미를 가지고 있다.

메모이제이션 기술은 주로 검색, HTML소스 코드 생성, 암호화, 데이터압축 및 변환과 같은 반복적인 작업에 사용된다.



Julia Hwang

디발자를 꿈꾸는 웹개발자의 블로그입니다.