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

[문제 링크]
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

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

[문제 요약]
“names.txt” 정렬이 안된 텍스트 파일을 읽어 모든 이름을 아래의 룰에 따라 연산한 합의 결과를 출력
COLIN 은 알파벳 순서로 정렬시 938번째에 존재한다.
C = 3
O = 15
L = 12
I = 9
N = 14
========
SUM = 53

nameScore = 938 * 53 = 49714

그렇다면 텍스트 파일에 포함된 모든 숫자의 nameScore의 합은?

[문제 풀이]
1. 파일을 읽는다.
2. 파일을 쉼표(,) 를 기준으로 split() 한다.
3. split() 된 파일을 정렬한다.
4. split() 의 결과를 반복하며 알파벳의 순서를 합산한다.

[소스코드]

"""
# 22_Names_scores.py
# Date: 2014. 08. 01
# Author: coozplz@gmail.com
# 학습내용
    1. 파일 읽기
    2. 리스트 정렬
    3. Character 를 ASCII 코드값으로 출력
"""

#이름 정보를 저장할 파일명
nameList = []

f = open("names.txt", "r")
# 파일을 읽는다.
line = f.read()

# 라인을 , 를 구분으로 자른다.
aStr = line.split(",")

for n in aStr:
    nameList.append(n)

print("Size =", len(nameList))

#이름을 정렬한다.
nameList.sort()

# 합산 점수를 저장
sumOfScores = 0

# 이름의 위치한 행의 번호
rowCount = 1


for name in nameList:
    nameCount = 0
    '''
    # 이름에 따옴표가 포함된 경우 제거
    '''
    name = name.replace("\"", "")
    for ch in name:
        '''
        # 이름을 한자씩 잘라서 ASCII 값으로 알파벳의 덧셈을 처리한다.
        # Ex) A = 1, B = 2
        '''
        nameCount += (ord(ch) - (ord('A')-1))

    sumOfScores += (nameCount * rowCount)
    rowCount += 1
print(sumOfScores)

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

[문제 원본]
Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n).
If d(a) = b and d(b) = a, where a ≠ b, then a and b are an amicable pair and each of a and b are called amicable numbers.

For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.

Evaluate the sum of all the amicable numbers under 10000.

[문제 풀이]

• 반복문에서 수를 감소시키며 숫자의 약수의 합을 구한다.
• 1에서 구해진 약수의 합의 수의 약수의 합을 구한다.
• 2에서 구해진 값과 진행 중인 숫자가 일치하면 Amicable Number로 인식한다.단, 1에서 구해진 약수의 합과 진행 중인 숫자가 같은 경우는 제외한다.

[소스 코드]

"""
# 19_Amicable_Numbers.py
# Date: 2014. 07. 31
# Author: coozplz@gmail.com
"""
num = 10000
sumOfAmicable = 0

while(num > 0) :
    sumOfDivisor = 0
    for i in range(1, num):
        if(num % i == 0):
            # 약수의 합을 구한다.
            sumOfDivisor = sumOfDivisor + i

    sumOfDivisor2 = 0
    for i in range(1, sumOfDivisor):
        if(sumOfDivisor % i == 0):
            # 약수의 합을 구한다.
            sumOfDivisor2 = sumOfDivisor2 + i


    """
    # 약수의 합과 수가 일치하지만 두수가 동일한 경우는 제외한다.
    # 예) 28 // 28
    #      6 // 6
    """
    if(sumOfDivisor2 == num and num != sumOfDivisor) :
        print("AmicableNumber=", num, sumOfDivisor)
        sumOfAmicable = sumOfAmicable + num
    num = num - 1
print(sumOfAmicable)

문제 이해를 잘못해서 시간이 엄청 걸렸습니다.

제출을 하면 어디가 잘못되었는지가 나오지 않기 때문에 문제를 정확하게 파악해야 됩니다.

이번에 실수는 1901~2000까지 일요일의 수를 카운팅 하는건줄 알았는데 알고보니 월의 처음 시작일이 일요일인 것만 찾는 문제였습니다.

소스코드에 불필요한 부분이 많이 있더라도 파이썬에 익숙해보고자 하는 일이기 때문에 … 이해 부탁드립니다.

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

[문제 원본]
You are given the following information, but you may prefer to do some research for yourself.

1 Jan 1900 was a Monday.
Thirty days has September,
April, June and November.
All the rest have thirty-one,
Saving February alone,
Which has twenty-eight, rain or shine.
And on leap years, twenty-nine.
A leap year occurs on any year evenly divisible by 4, but not on a century unless it is divisible by 400.
How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?

[풀이 방법]
1. 1900~1901년까지 월의 시작요일이 일요일인 개수를 구한다.
2. 1900~2000년까지 월의 시작요일이 일요일인 개수를 구한다.
3. 2의 결과에서 1의 결과를 제거한다.

위와 같이 한 이유는 문제에서 주어진 처음 시작 요일이 1900년 1월 1일 이기 때문입니다.
[소스 코드]

#
#19_Counting_Sundays.py
#
months = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
days = ["MON", "TUE", "WED", "THU", "FRI", "SAT", "SUN"]

'''
#### 함수 정의 부분 ####
'''
def countingSundays(sYear, eYear):
    """ 주어진 기간 동안에 월의 시작요일이 일요일인 항목은 구한다.
    :param sYear: 시작 월
    :param eYear: 마지막 월
    :return:       월의 시작 요일이 일요일인 개수
    """

    count = 0
    sumOfDays = 0

    while(sYear <= eYear) :
        if((sYear % 4 == 0 and sYear%100 != 0) or (sYear % 400 == 0)) :
            months[1] = 29
        else :
            months[1] = 28
        for i in months :
            if(days[sumOfDays % 7] == 'SUN'):
                count = count+1
            sumOfDays = sumOfDays + i
        sYear = sYear + 1

    return count

'''
#### 메인 실행 부분 ####
'''
sumUtil1901 = countingSundays(1900, 1900)
print("Sundays fell on the first of the month until 1901 =", sumUtil1901)
print("Sundays fell on the first of the month = ", countingSundays(1900, 2000) - sumUtil1901)

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

[문제 원본]
n! means n × (n − 1) × … × 3 × 2 × 1

For example, 10! = 10 × 9 × … × 3 × 2 × 1 = 3628800,
and the sum of the digits in the number 10! is 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27.

Find the sum of the digits in the number 100!

[풀이방법]
1. 반복문을 통해 팩토리얼의 값을 구한다.
2. 팩토리얼 값을 String 타입으로 변경한다.
3. 변경된 String 값을 한자씩 추출하여 Integer 타입으로 변경한다.
4. 변경된 Integer 타입을 더한다.

[소스코드]

#20_FactorialDigitSum.py

num = 100
sum = 1
while(num > 0) :
	sum = sum * num
	num = num -1

strNum = str(sum)
num = 0
for i in range(0, len(strNum)):
	#print(strNum[i], end=' ')
	num = num  + int(strNum[i])

print("DigitSum=", num)

[문제 링크]
http://projecteuler.net/problem=16
[문제 원본]
2^15 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.

What is the sum of the digits of the number 2^1000?

[소스 코드]

#python PowerDigitSum.py

input = input("number = ")
count = 1000
sum = 1;
for i in range(1, count+1):
    sum = sum * int(input)
str = str(sum)
print("Sum=", sum)

digitSum = 0
for j in range(0, len(str)):
    # print(str[j])
    digitSum = digitSum + int(str[j])
print("Digitsum=", digitSum)
print("Done")

[결과]
number = 2
Sum= 107150860718626732094842504906000181056140481170553360744375038837035105112
49361224931983788156958581275946729175531468251871452856923140435984577574698574
80393456777482423098542107460506237114187795418215304647498358194126739876755916
5543946077062914571196477686542167660429831652624386837205668069376
Digitsum= 1366
Done

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

[문제 원본]
By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10 001st prime number?

[문제 설명]
2에서 6번째에 해당하는 소수는 13이다. 그렇다면 10001번째 해당하는 소수는 몇인가?

[소스코드]

# problem_7.py
import custom_math
count = input("Input: ");
i = 2
while 1 : 
    if(custom_math.isPrime(i)) :
        count = count -1
    if(count == 0): 
        break
    i = i+1
print("Number is =", i)

# custom_math.py
import math
 
def isPrime(n): 
    result = True
    for i in range(2, int(math.sqrt(n)) + 1):
        if n%i == 0:
            result = False
            break
     
    return result

[결과]
Input: 10001
(‘Number is =’, 104743)