문제

https://programmers.co.kr/learn/courses/30/lessons/12953

나의 코드

"""
1. 아이디어
최소 공배수 구하는 문제인데 식을 몰라서 비효율 적이게 풀 수 있을거 같다.

2. 시간복잡도
O(N^2)
"""

def solution(arr):
    
    for i in range(1, 100000000+1):
        for j in arr:
            if i % j == 0: # 만약 i의 약수이면 계속 반복문을 돌고
                continue
            else: # i의 약수가 아니면 break
                break
        else: # 이 코드는 i의 약수가 아니고 정상적으로 반복문이 종료되면 수행된다.
            return i
    

다른 사람의 코드

def gcd(a, b): # 유클리드 호제법
    
    while b > 0:
        a, b = b, a % b
        
    return a
 
def lcm(a, b): # 최소 공배수
    return a * b / gcd(a,b)
 
 
def solution(arr):
    answer = 1
    
    for num in arr:
        answer = lcm(num, answer)
    
    return answer
    

느낀점

최대공약수, 최소공배수 구하는 식을 까먹지 말고 기억해야 겠다.

최대 공약수란, 숫자 a, b가 주어졌을 때, 공통되는 약수 중에서 최대 값을 의미한다.

• 최대공약수 구하기

1. a, b 각각의 약수를 구해서 공통되는 약수중에서 가장 큰 값을 찾는 방법
   -> 찾지 않아도 되는 약수들 까지 구해야하기 때문에 효율적이지 않다.

2. 유클리드 호제법
   유클리드 호제법이란, 숫자 a, b가 있을 때, a를 b로 나눈 나머지와 b 의 최대 공약수 는 a 와 b 의 최대 공약수 가 같다는 것을 의미한다.

그럼, 계속해서 a 를 b로 나누어서 b 가 0이 될때 까지 반복을하면, 남는 a 값이 바로 최대 공약수 이다.

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

최소 공배수란, 숫자 a, b가 주어졌을 때, a, b의 곱을 a, b의 최대 공약수로 나누면 나오게 된다.

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

하지만 다음과 같이 math 라이브러리를 이용해서 구해도 된다.

import math

print(math.gcd(20, 45)) # 5
print(math.lcm(10, 20, 35)) # 140

• math.lcm은 python version 3.9 이상 이어야 한다.