본문 바로가기

프로그래밍/오일러프로젝트

(24)
[EP 048] ∑ i^i (i=1 ~ 1000) 의 마지막 10자리수 구하기 #!/usr/bin/python ############################################################################ # # Problem 48 # 18 July 2003 # 1 2 3 10 # The series, 1 + 2 + 3 + ... + 10 = 10405071317. # # Find the last ten digits of the series, # 1 2 3 1000 # 1 + 2 + 3 + ... + 1000 . ############################################################################ # Author : DwYoon # Date : 2007 04 12 def pow_mod(b..
[EP 050] 연속된소수의합이 다시 소수 무식한 방법으로 푼다. 루프를 빠져나오는 조건을 잘 줘야 빨리 끝난다. 소수를 구할 때, 나눌 수가 소수후보의 제곱근보다 크다면 빠져나오라는 조건을 빼면 시간이 하염없이 걸리고, 연속된소수의 합이 다시 소수인 모든 수를 구하는 것이 아니고, 그 소수 갯수의 최대값을 구한다는 조건을 for 루프에 잘 적용하면 또 시간을 더 단축할 수 있다. 물론 깔끔함은 훼손되지. /* * http://projecteuler.net/index.php?section=problems&id=50 Problem 50 15 August 2003 The prime 41, can be written as the sum of six consecutive primes: 41 = 2 + 3 + 5 + 7 + 11 + 13 This is t..
[Euler Project 134] 1219는 소수 19로 끝나는 23의 배수 5가 아닌 소수의 배수는 마지막 자리수가 1, ... , 9 까지 모두 나온다.
[Euler Project 089] 로마숫자 최적화 로마숫자를 최적화 하는 코드를 짜라. 로마숫자에 익숙하지 않아서 힘들었다. 이게 맞는 건지는 모르겠다. 그냥 일, 십, 백이 네 개 연속으로 등장하는 것에 대해서만 고치도록 짰다.
[Euler Project 114] 몇 칸짜리 격자를 빨간색이나 검은 색으로 채운다. 이 조건만 있으면 단순히 2의 n승으로 답이 끝난다. 조건은 빨간색은 최소한 연속 3칸 이상 이어져 있어야 한다는 조건이 추가되어 문제가 복잡해진다. 제일 처음 칸 부터 한칸씩 빨간색을 칠할 지, 검은 색을 칠할지를 결정하는 함수를 구성했고, 이 함수를 재귀적으로 불렀다. 어차피 한 칸을 채운 다음에는 남은 몇 칸에 대해 고민하는 것은 똑같으니까. 이전에 빨간색이 아니었다면, 빨간색이 오면 3칸이 무조건 칠해진다. 경우의 수가 줄어든다. 그리고 마지막에 3칸 미만이 남아 있으면 무조건 검정색이 들어갈 수밖에 없다. 뭐 이런 조건들을 함수에서 분기해야 했다. 처음에는 완성된 격자를 다 프린트하는 함수를 만들어서 예시로 주어진 7칸 짜리를 해 봤고, 50을 ..
[Euler Project 090] itertools 의 combinations 를 가져다 씀. 좀 반칙성으로 브루트포스 풀이. 그냥 문제의 요구를 그대로 코딩했음. 문제가 좀 애매한 부분이 있었는데, 두 주사위를 다른 것으로 볼 것이냐 아니면 같은 것으로 볼 것이냐... 그래서 계속 답이 틀렸음. 검색해서 다른 사람의 풀이를 보고 문제의 의도를 알아낼 수 있었음.
[Euler Project 091] 직각삼각형 갯수 구하기 (2) 주어진 레인지 안의 두 점을 잡아서 원점과 연결한 삼각형이 직각삼각형인 갯수를 구하는 문제임. 벡터의 내적과 외적의 성질을 이용해서 간단한 식으로 푼다. 내 컴퓨터에서 10초정도 걸린다. 아무래도 모든 가능한 점을 다 돌면서 검사를 하다보니.과거에 풀었던 것은 조건을 나눠서 복잡했었는데, 이 쪽이 코드는 더 간단하다. 비슷하게 풀었던 다른 문제도 있었던 듯.
[Euler Project 164] 연속된 세 개의 자리수의 합이 9를 넘지 않는 20자리수 연속된 세 개의 자리수의 합이 9를 넘지 않는 20자리수의 갯수를 구하라. ( http://projecteuler.net/index.php?section=problems&id=164 ) def get_count(n1, n2, remain): #print " "*(20 - remain), n1, n2, remain if cache.has_key((n1, n2, remain)): return cache[(n1, n2, remain)] count = 0 sum = n1 + n2 if remain == 1: cache[(n1, n2, remain)] = 10 - sum return 10 - sum for n3 in range(10 - sum): count += get_count(n2, n3, remain - 1..