#21 알고리즘연습 최소공배수와 최대공약수 PYTHON|벽에그린나의키

2019년 4월 1일 월요일

#21 알고리즘연습 최소공배수와 최대공약수 PYTHON

최대공약수와 최소공배수

문제 설명

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

제한 사항

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

입출력 예

n	m	return
3	12	[3, 12]
2	5	[1, 10]

입출력 예 설명

입출력 예 #1
위의 설명과 같습니다.

입출력 예 #2
자연수 2와 5의 최대공약수는 1, 최소공배수는 10이므로 [1, 10]을 리턴해야 합니다.

문제풀이 IDEA

최대공약수와 최소공배수의 특징에 대해서 생각을 해보았는데
최대공약수의 경우 두 수의 공약수중에 느낌으로 찾았고 최대 공배수도 두 수를 비교하여 느낌적으로 찾아서 실제로 그 느낌으로 코드를 짜기는 어려웠다

그래서 나온게 첫번째 코드인데
두 수중 1개의 숫자에 대해 약수list를 만든다음 큰 약수부터 차례차례 다른 수를 나눌 수 있는지 체크해주고

최소공배수는 최악의 경우 두 숫자끼리 서로의 곱이 최소공배수가 되므로
다른 한 숫자보다 작은 범위에서 곱 연산을 진행해 결과가 다른 한숫자의 배수인지 확인해주는 절차를 거쳤다

이 외에도
소인수분해를 해서 최소공배수 최대공약수를 구하려는 방법도 구상해봤지만 해당 과정안에서 반복문이 너무 많이 들어가서 연산 속도가 저하될 것 같은 생각에 사용하지 않았다.

나의 코드

def solution(n, m):
    answer = []
    if m % n == 0:    #이 연산의 가정은 m이 n보다 큰수이다를 가정했다.
        return [n,m]   그럼 최대공약수, 최소공배수 모두 서로가 되므로 그냥 return
    else:
        temp = [i for i in range(1,n+1) if n%i == 0]  #위에서 n을 더 작은 숫자로 가정했으니 n의 약수들의 list를 만든다
        while len(temp)>0:                            
            tempele = temp.pop()                      #list의 뒷부분일수록 큰 약수가 위치해 있으므로 최.대 공약수를 찾기위해서는 
            if m % tempele == 0:                       뒤에서 부터 pop을 해준다
                answer.append(tempele)
                break                                #찾으면 break를 통해서 반복문을 탈출
        for i in range(1,n+1):                       #최소공배수를 찾기 위해서 다른 숫자보다 작은 자연수들을 차례차례 곱해서 결과가 
            if i*m % n ==0:                           다른 숫자의 배수인지 확인해준다
                answer.append(i*m)
                break
        return answer

다른 코드(최소공약수 알고리즘을 찾으면 나오던..)

def solution(n, m):
    def gcd(n,m):             #이 알고리즘에서는 유클리드 호제법을 사용하여 계산
        while(m):              여기서는 m이 나중에 나머지의 포지션을 잡으므로 m의 유무에 따라 반복을 설정해주자
            n,m = m,n%m       #유클리드 호제법에서 두번째 인자에는 나머지가 들어간다
        return n
    return [gcd(n,m), n*m/gcd(n,m)]     해당 값은 최대공약수, 그리고 최소공배수*최대공약수가 n*m임을 이용해줬다

유클리드 호제법에 대해 정수론 시간에 배웠었는데 실생활에서의 활용예제를 못 보다가 막상 마주치니까 떠오르지 않았다
하지만 이를 코드로 구현하니 정말 간결하고 빠르게 gcd 가 구해지는 것을 알수 있다.

유클리드 호제법의 예시

180 ＝ 108×1 + 72
      108 ＝ 72×1 ＋ 36
       72 ＝ 36×2

위의 예시를 보면 알수 있듯 // 이런 방향으로 애들이 착착 내려오는 것을 알수 있다. 따라서 n,m에서 m, n%m 이 되고 이게 계속 반복되다가 n,0 이 되면 n이 m으로 나눠떨어진다는 의미이므로 해당 값이 최대공약수가 된다

최소공배수는 n*m/gcd()에 대해서는 소인수분해에서 최소공배수와 최대공약수 구하는 부분에서 알수 있는 성질이다

42 = 3^2 * 7^1
15 = 3^1 * 5^1

최대공약수 = 공통으로 가지고 있는 소수 3^1
최소공배수 = 3^2 * 7^1 * 5^1 (공통으로 가진 소수는 최대 차수)

따라서 우리는 최대공약수 * 최소공배수 = A * B임을 알수 있다.

출처: 프로그래머스

벽에그린나의키

2019년 4월 1일 월요일