본문 바로가기

오일러프로젝트

 (27)
[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 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..
[Euler Project 078] 분할함수 (Partition Function) 76, 77번을 풀었던 방법으로 풀었는데, 끝까지 계산하지 못하고 오버플로우가 났다. 삼각형 형태로 메모리가 늘어나서 13000 까지 찍고 죽는 것이었다. 그래서 위키백과의 점화식을 이용하여 푸는 코드를 짜서 풀었다. 점화식은 2차원인 아닌 1차원으로 기억하고 있으면 되서 답을 내 줬다. 죽는 코드와 죽는 모습 #!/usr/bin/env python # euler 78 P = [] n = 0 P.append([]) P[n].append(0) # P[0][0] n = 1 P.append([]) P[n].append(0) # P[1][0] P[n].append(1) # P[1][1] n = 2 while 1: cnt = 0 P.append([]) for i in range(n+1): if i == 0: cn..
[Euler Project 077] 소수의 합으로 표현하는 가짓수 스프레드시트로 표현한 배열이랑, 코드에서 구하는 배열이랑 의미가 조금 다르다. 아래 코드에서는 누적값을 구한다. 그래서 계산의 summation 루프를 줄인다. 위 그림은 이해를 좋게 하기 위해 누적으로 표현하지 않았다. 가로축은 합이 되는 수, 세로축은 소수이다. 2, 2 는 2를 2를 최소한 한번 포함하여 2 이하의 소수들의 합으로 표현하는 갯수로 1이다. 10, 5 는 10을 5를 최소한 한번 포함하여 5 이하의 소수들의 합으로 표현하는 갯수이다. 5+5와 5+3+2가 있는데, 최대 소수인 5를 10에서 뺀 나머지인 5에 대해 경우의 수를 summation 하여 구할 수 있다. 아래는 파이썬 코드. 2차원 배열이 위 스프레드시트의 것과 다른 점 주의하라. #!/usr/bin/env python # ..

티스토리툴바