0722 TodayReview

너무 더워서 그런가 문제가 잘 안풀려서 쉬운문제부터 풀었다..
카카오 코테 후반부 문제들만 남았는데, 너무 어렵고 답을 봐도 한번에 이해가 가지 않아서 이 체력과 집중력에 푸는건 무의미하다 싶다.
아무래도 풀었던 문제를 한번 더 풀어보는게 어떨까 싶다.. 아직 많이 남았지만 ㅠㅠ

Today PS : N개의 소수 찾기

문제 자체는 어렵지 않았는데, 그 외의 python의 최대공약수, 최소공배수를 구하는 법을 확인 할 수 있었다.

#0721
from math import gcd

def lcm (x,y):
    return x*y//gcd(x,y)

def solution(arr):
    answer = 0
    temp = [] 
    temp.append(arr.pop(0))
    
    while True: 
        temp.append(lcm(temp.pop(0),arr.pop(0)))
        if len(arr)==0:
            break
    
    answer = temp[0]
    return answer

최대공약수 (Greatest Common Divisor)

최대공약수는 주어진 두 수 x,y에서 x의 약수이면서 y의 약수인 수 중 최대값을 의미
-완전탐색으로 최대공약수를 구할 수도 있지만
-유클리드 호제법 (Euclidean algorithm)을 이용하면 간단하게 계산 가능

유클리드 호제법
최대 공약수를 구하는 함수를 gcd(x,y)라고 가정
x%y = 0 이라면 gcd(x,y) = y가 성립
x%y != 0 이라면 gcd(x,y) = gcd(x,x%y)가 성립
2번이 될 때까지 2-3번을 반복

1) 유클리드 호제법을 코드로 구현

def gcd(x,y):
	#y가 0이 될 때 까지 반복
    while y: 
    	#y를 x에 대입
        #x를 y로 나눈 나머지를 y에 대입
        x,y = y, x%y
        
    return x

2) 내장함수 math 모듈에서 기능 제공

from math import gcd

x,y = 1071,1029

print(gcd(x,y))
#21

최소공배수 (Least Common Multiple)

최소공배수는 x와 y의 공통된 배수 가운데 최솟값을 의미한다.
최소공배수는 주어진 수인 x,y의 곱에서 x,y의 최대공약수를 나눈 몫을 return

from math import gcd

def lcm():
	return x*y//gcd(x,y)