python

[Python] 5-SmallestMultiple

알고리즘은 생각하지 않고 하루에 한 문제씩 풀면서 파이썬이란 언어와 친해지려고 합니다..
혹시 보시고 잘못된 부분이나 지적하실 부분이 있으면 댓글로 남겨주세요..

[문제 링크]
http://projecteuler.net/problem=5

[문제 요약]
1에서 20으로 모두 나눠지는 가장 작은 수를 구하시오..

[풀이 리뷰]
알고보면 간단한 문젠데 이해가 안되서 고민을 좀 했습니다.
프로젝트오일러에 나온 문제들은 대부분 1분내외로 풀어야 한다고 합니다.
제가 풀려고 했던 방법은 2의 배수중 20 보다 작은 가장 큰 수, 3의 배수중 20보다 작은 가장 큰수…. + 20이하의 모든 소수로 나눠지는 수를 계산하려고 했습니다.

나름 머리를 쓴다고 쓴게 반복을 최소화해서 속도를 높여보자였는데 간단한 방법이 있었습니다.

최소공배수(Least Common Multiple)를 이용하는 방법입니다.

lcm(lcm(lcm(lcm(1,2),3),4)…., 20)
위와 같은 방법으로 하면 연산을 많이 하지 않고도 답을 구할 수 있습니다.

[소스 코드]

"""
# 5_SmallestMultipl.py
# Date: 2014. 08. 04
# Author: coozplz@gmail.com
"""
import time

sTime = time.clock()
def gcd(a,b):
   """
   최대 공약수를 구하는 함수
   :param a: 숫자 입력값 1
   :param b: 숫자 입력값 2
   :return:최대 공약수
   """
   m = max(a,b)
   n = min(a,b)
   while n != 0:
       t = m % n
       (m,n)=(n,t)
   return abs(m)


"""
# 1. 숫자 1과 숫자 2의 최소공배수를 구한다.
# 2. 1의 결과와 3의 최소공배수를 구한다.
# ....
# 이전의 결과와 20의 최소공배수를 구한다.
"""

gcdValue = 1
for j in range(1, 21):
    # 최소 공배수를 구한다
    gcdValue = int(gcdValue * j / gcd(gcdValue, j))
    i = j
print(gcdValue, "최소공배수 이용=", (time.clock() - sTime) * 100)

"""
# 단순 무식하게 반복문으로 1씩 증가하면서 모두 해본다.
"""
sTime = time.clock()
num = 1
while True:
    found = True
    for i in range(1, 21):
        if num % i != 0:
            found = False
            break
    if found:
        break
    num += 1
print(num, "반복문만 사용=", (time.clock() - sTime) * 100)

[풀이 시간]
최소공배수 이용= 0.0030000000000000512
반복문만 사용= 14033.343700000001

기본

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Google+ photo

Google+의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

%s에 연결하는 중