프로젝트 오일러 5번문제 - 최소공배수

1~20까지 모두 나누어떨어지는 가장 작은수, 즉 공통의 배수, 최소공배수를 구하는 문제입니다.

Smallest multiple

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

최소공배수는 두수를 곱해서 최대공약수로 나누어 주면 됩니다. 여러숫자의 최소공배수일때는 두수씩 순차적으로 계산해주면 최종나오는 최소공배수가 전체수의 최소공배수가 됩니다.
그러면 먼저 최대공약수(gcd)를 먼저 구해야 되겠네요.(최소공배수:lcm)

방법 1

최대공약수로 계산

def get_gcd(num1,num2):
    i=1
    while i <= num2:
        if num1%i==0 and num2%i==0:
            gcd=i
        i+=1
    return gcd
 
print(get_gcd(12,18))
print(get_gcd(27,63))

6
9

가장 기본적인 방법입니다. 두수중 작은수를 기준으로 1부터 작은수까지 루프를 돌면서, 두수를 동시에 다 나누어 보고, 나누어 떨어지면 공약수이고, 마지막 공약수가 최대공약수가 되겠습니다.

또는 math 모듈의 gcd() 함수 이용

1 2	`import` `math` `math.gcd(12,18)`

파이썬내의 math 모듈을 import 해서 모듈내의 gcd 함수를 간단하게 이용할수도 있습니다.

help(math) 라고 입력하면 간단한 사용법과 함수목록이 나옵니다.

1 2	`import` `math` `help(math)`

Help on built-in module math:
.
.
.   
    gcd(...)
        gcd(x, y) -> int
        greatest common divisor of x and y
.
.
.

math 모듈을 이용할때는 gcd()함수로 정수형이 들어가는지 확인해야 합니다. 나눗셈의 결과로 float 형이 생성되기 때문에, int()함수로 정수형숫자로 바꿔줘야 합니다.

import math
 
lcm=1
for i in range(1,21):
    gcd = math.gcd(lcm,i)
    lcm = int(lcm*i/gcd)
    print(i,lcm)

방법 2

프로젝트 오일러 포럼에 있는 다른유저가 만든 코드인데, 몇가지 생소한 문법이 있어서 가져와봤습니다.

from functools import reduce
 
n = reduce(lambda x, y: x*y, range(2,21)) #1~20까지 다 곱하기
print(n)
 
for i in range(20,1,-1):
    print(i,n,n/i)
    if all(not n/i%j for j in range(2,21)): #1~20까지 다 나누어 떨어지면 
        n = n//i         #원래수를 나누어서 크기를 줄임.
        print(i,n)
 
print(n)

1~20까지 먼저 다 곱해놓고, 거꾸로 나눠가면서, 1~20까지 나누어봐서 한꺼번에 나누어 떨어지면 크기를 줄여나갑니다. 3번문제에서 썼었던 brute force 방법이라고 할수 있겠네요.

reduce() 함수

https://www.python-course.eu/python3_lambda.php

>>> import functools
>>> functools.reduce(lambda x,y: x+y, [47,11,42,13])
113
>>>

reduce()함수는 순차적으로 계산을 해 나가는 함수입니다. lambda 로 정의된 어떠한 연산을 앞에서부터 두번째 매개변수인 어떤 범위에 대해서 순서대로 계산해서 최종 결과를 return 하는 함수입니다. 이 경우엔, 전체수를 합하는 연산과 같네요.

lambda operation

1	`lambda` `x,y: x+y, [47,11,42,13]`

람다 함수는 함수안에 작은 함수라고 보시면 될거 같네요. javascript를 공부하신 분은 Arrow function( () => {} ) 을 떠올리시면 될것 같습니다. 완전히 같진 않지만요. 콜론(:)앞쪽 x,y를 넘겨줘서, 콜론 뒤의 x+y 의 연산을 수행해서 리턴하라는 의미입니다.

if all():

all() 안의 조건이 "모두" 참인지를 판단합니다. 하나라도 참이 아니면 False를 반환합니다.
예를 들어, 10 이 2와 5로 동시에 나누어 떨어지는지를 알고 싶으면,

1 2	`if` `all(10%i` `==` `0` `for` `i` `in` `[2,5]):` `print('yes')`

yes

또는

1 2	`if` `all(not` `10%i` `for` `i` `in` `[2,5]):` `print('yes')`

yes

두 번째 코드는 나머지 연산(10%i)자체를 논리연산자를 대신해 사용한것입니다. 나누어 떨어지면 값이 0(논리값 False)이 되어서 if문이 조건을 만족하지 않는것으로 판단하기 때문에, not을 붙여주면 반대로 true가 되어서, 원하는 동작이 실행됩니다.

if not all():

not을 all()앞쪽에 붙여주면, 논리적 반대값이 아니라, all 의 부정, 즉 "모두 참이 아닐때"를 의미합니다. 즉 하나라도 거짓(혹은 0)이 있으면, 참이 되어서 그다음 문장을 실행합니다. 햇갈릴테니 직접 한번 해보세요.

현재 버전	2018-04-20 02:54:34
선택 버전