whatismyblank

안녕하세요! 거의 일년만에 쓰는 포스팅이네요... 

다시 차근차근 열심히 해보겠습니다! 

문제) n개의 숫자를 담은 배열 arr이 입력되었을 때, 이 수들의 최소공배수를 반환하는 함수를 작성하라. 

여기서 알아야 할 점은 

A. 숫자가 담긴 배열이 input 값이다.

B. 최소공배수를 구해야 한다. 

로 파악할 수 있습니다. 

A는 반복문으로 해결이 가능합니다. 

B는 최대공약수와 최소공배수의 원리와 알고리즘을 알고 있어야 해결할 수 있습니다. 

1. 최대공약수(gcd)를 구하는 알고리즘, 유클리드 알고리즘 Greatest Common Divisor

먼저 최대공약수를 구하는 알고리즘에 대해 알아보겠습니다. 

최대공약수를 구하는 알고리즘에는 여러가지가 있습니다.

시간 복잡도와 공간 복잡도를 고려하지 않는다면, 단순하게 모든 약수를 구해 리스트에 넣고 비교하는 알고리즘이 있을 수 있습니다. 두 수의 최대공약수를 구한다고 했을 때, 이 알고리즘의 시간복잡도는 O(n^2) 또는 O(n)이 됩니다. 

(두 수의 약수를 모두 구하거나, 한 개의 수만 약수를 구할 수 있기 때문입니다.)

최대 공약수를 구하는 가장 좋은 알고리즘은 "유클리드 알고리즘" 입니다. 

(알고리즘 수업 기말고사에 나왔던 기억이 나네요!)

def gcd(a,b):
    while b!=0:
        r=a%b
        a=b
        b=r
    return a

유클리드 알고리즘은 이와 같이, gcd(a, b) -> gcd(b, mod b) 와 같은 구조를 반복하는 알고리즘 입니다.

예를 들어 gcd(12,4)의 경우에는

gcd(12,4) 

= gcd(4,0) 이 되어 최대공약수는 a인 4가 됩니다. (b가 0이 되었기 때문에 while문이 종료되고 a값이 return 됩니다.)

유클리드 알고리즘의 장점은 시간복잡도가 O(logN)이라는 것입니다. 

2. 최소공배수(lcm)를 구하는 알고리즘, Least Common Multiple

최소공배수를 구하는데 왜 최대공약수를 구하는 알고리즘을 설명했을까요?

최소공배수와 최대공약수는 연관이 있기 때문입니다. 

a, b 두 자연수의 최대공약수 gcd 최소공배수 lcm을 구했을 때,

a x b = gcd x lcm 입니다. 

그렇게 때문에 이전에서 유클리드 알고리즘을 설명했습니다. 

3.  1, 2를 바탕으로 작성된 알고리즘

def gcd(a,b):
    while b!=0:
        r=a%b
        a=b
        b=r
    return a

def solution(arr):
    
    for i in range(len(arr)-1):
        temp_gcd=gcd(arr[i],arr[i+1])
        #최소공배수 구하기
        arr[i+1]=(arr[i]*arr[i+1])/temp_gcd
        print(arr)        
    

    return arr[len(arr)-1]

저는 내장함수 gcd를 사용하지 않고 제가 정의하여 사용했습니다. 

(사실 내장함수가 있는 걸 까먹었습니다... ㅎㅎ)

그 후, 포스팅 초반에 언급했던 것과 같이 반복문을 이용하여 최대공약수를 구한 후 최소공배수를 계산했습니다. 

lcm = a x b / gcd 이기 때문입니다. 

여기서 주의해야 할 점은 두 수의 최대공배수를 구하는 것이 아니라 n개의 수가 있는 배열의 최소 공배수를 구하는 것이라는 점입니다. 

최소공배수를 구한 후, 해당 최소공배수와 다른 수의 최소공배수를 구하는 과정을 반복해야합니다. 

리스트를 놓고 설명하면, 

0번째와 1번째의 최소공배수를 구한 값을 다시 1에 넣고

1번째와 2번째의 최소공배수를 구한 후 그 값을 다시 2에 넣습니다.

이러한 과정을 반복하여, 

마지막에는 4번째와 5번째의 최소공배수를 구한 후, 그 값을 5에 넣습니다. 

이 부분에서는 list index out of range를 항상 조심해야합니다. 

제가 항상 index range 오류가 납니다... 상기시키려고 적습니다. 

참고) gcd 내장함수 사용하기 

Python의 math 모듈에서는 gcd뿐만 아니라 lcm 모듈도 제공합니다. 

from math import gcd

def solution(arr):
    
    for i in range(len(arr)-1):
        temp_gcd=gcd(arr[i],arr[i+1])
        #최소공배수 구하기
        arr[i+1]=int((arr[i]*arr[i+1])/temp_gcd)       

    return arr[len(arr)-1]

math모듈 중 gcd 함수만 사용하기 위해, from 모듈이름 import 함수이름 의 형태로 선언했습니다. 

(모듈만 불러오는 것과 모들 중 하나의 함수만 불러오는 것 중 무엇이 더 효율적인지는 아직 모르겠습니다.

일단 가져온다는 점이... 이건 후에 알아봐야 할 것 같습니다.) 

gcd 함수를 사용했을 때, 이전 코드에서 변경해야 할 점은,

두 자연수의 곱을 최대공약수로 나눌 때 사용한 '/' 연산자 때문에 float가 반환된다는 점이었습니다.

gcd 함수는 integer만 적용할 수 있습니다. 그렇기 때문에 int형으로 변환하였습니다.