본문 바로가기

오일러프로젝트

[오일러프로젝트] 32번문제 1부터 n까지의 각 숫자를 한번씩만 써서 만들 수 있는 숫자를 팬디지털(pandigital)이라고 합니다. 예를 들면 15234는 1부터 5의 숫자가 한번씩만 쓰였으므로 1 ~ 5 팬디지털입니다. 7254라는 숫자는 그런 면에서 특이한데, 39 × 186 = 7254 라는 곱셈식을 만들 때 이것이 1 ~ 9 팬디지털이 되기 때문입니다. 이런 식으로 a × b = c 가 1 ~ 9 팬디지털이 되는 모든 c의 합은 얼마입니까? (참고: 어떤 c는 두 개 이상의 (a, b)쌍에 대응될 수도 있는데, 이런 경우는 하나로 칩니다) 일단 약수를 구한 후 0이 있는 것 제외, a,b,c 합친 길이가 9가 아닌 것 제외 하는 방식으로 brute-force. 다만 상한선을 100000으로 잡은 것은 어림짐작... Pyt.. 더보기
[오일러프로젝트] 31번문제 영국의 화폐 단위는 파운드(£)와 펜스(p)이고, 동전의 종류는 아래와 같습니다. 1p, 2p, 5p, 10p, 20p, 50p, £1 (100p), £2 (200p)이 동전들을 가지고 2파운드를 만드는 방법은 다양할 것입니다. 예를 하나 들면 이렇습니다. 1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p2파운드를 만드는 서로 다른 방법은 모두 몇가지나 있습니까? brute-force로 풀었는데 시간이 상당히 걸린다. 문제 풀이 후 좀 더 찾아보니 전형적인 Dynamic Programming 알고리즘의 문제라고 한다. 아래의 내 코드가 약 1분 정도가 소요되는데 DP 방식으로 구현된 이 코드 http://blog.dreamshire.com/2009/03/31/project-eul.. 더보기
[오일러프로젝트] 30번문제 각 자리의 숫자를 4제곱해서 더했을 때 자기 자신이 되는 수는 놀랍게도 단 세 개밖에 없습니다. 1634 = 14 + 64 + 34 + 44 8208 = 84 + 24 + 04 + 84 9474 = 94 + 44 + 74 + 44(1 = 14의 경우는 엄밀히 말해 합이 아니므로 제외합니다) 위의 세 숫자를 모두 더하면 1634 + 8208 + 9474 = 19316 입니다. 그렇다면, 각 자리 숫자를 5제곱해서 더했을 때 자기 자신이 되는 수들의 합은 얼마입니까? 문제를 푸는 로직 자체는 단순한데 계속 답을 틀려서 좀 생각해보니 문제에서 제시된 상한선이 없다. 혼자 힘으로는 상한선을 찾지 못해 검색의 힘을 빌려보니 6자리 수일 때 최대합은 (9**5)*6으로 354294가 나온다. 7자리 수일 때 최대합.. 더보기
[오일러프로젝트] 29번문제 2 ≤ a ≤ 5 이고 2 ≤ b ≤ 5인 두 정수 a, b로 만들 수 있는 ab의 모든 조합을 구하면 다음과 같습니다. 22=4, 23=8, 24=16, 25=32 32=9, 33=27, 34=81, 35=243 42=16, 43=64, 44=256, 45=1024 52=25, 53=125, 54=625, 55=3125여기서 중복된 것을 빼고 크기 순으로 나열하면 아래와 같은 15개의 숫자가 됩니다. 4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125 그러면, 2 ≤ a ≤ 100 이고 2 ≤ b ≤ 100인 a, b를 가지고 만들 수 있는 ab는 중복을 제외하면 모두 몇 개입니까? 문제는 평이한 수준이나 perld에서 Set 사용을 위한 .. 더보기
[오일러프로젝트] 28번문제 숫자 1부터 시작해서 우측으로부터 시계방향으로 감아 5×5 행렬을 만들면 아래와 같이 됩니다. 21 22 23 24 25 20 7 8 9 10 19 6 1 2 11 18 5 4 3 12 17 16 15 14 13 여기서 대각선상의 숫자를 모두 더한 값은 101 입니다. 같은 방식으로 1001×1001 행렬을 만들었을 때, 대각선상의 숫자를 더하면 얼마가 됩니까? 대각의 위치를 찾는 문제일까.. 저런 행렬을 만드는 로직을 찾는 문제일까.. 한참 고민하다가.. 각 4 모서리의 수에서 패턴발견.. Python Ruby Perl perl도 python이나 ruby처럼 step을 줘서 돌릴 수 있는 방법이 있을 것도 같은데....흠 더보기
[오일러프로젝트] 27번문제 오일러는 다음과 같은 멋진 2차식을 제시했습니다. n2 + n + 41이 식의 n에다 0부터 39 사이의 숫자를 넣으면, 그 결과는 모두 소수가 됩니다. 하지만 n = 40일 때의 값 402 + 40 + 41 은 40×(40 + 1) + 41 이므로 41로 나누어지고, n = 41일 때 역시 412 + 41 + 41 이므로 소수가 아닙니다. 컴퓨터의 발전에 힘입어 n2 − 79n + 1601 이라는 엄청난 2차식이 발견되었는데, 이것은 n이 0에서 79 사이일 때 모두 80개의 소수를 만들어냅니다. 이 식의 계수의 곱은 -79 × 1601 = -126479가 됩니다. 아래와 같은 모양의 2차식이 있다고 가정했을 때, n2 + an + b (단 | a | < 1000, | b | < 1000)0부터 시작하.. 더보기
[오일러프로젝트] 26번문제 분자가 1인 분수를 단위분수라고 합니다. 분모가 2에서 10까지의 단위분수는 아래와 같습니다. 숫자 위에 찍힌 점은 순환마디를 나타내는데, 1/6의 경우 순환마디는 "6"으로 0.166666...처럼 6이 무한히 반복됨을 뜻합니다. 같은 식으로 1/7은 6자리의 순환마디(142857)를 가집니다. d 를 1000 이하의 정수라고 할 때, 단위분수 1/d 의 순환마디가 가장 긴 수는 무엇입니까? 풀지못했다. 문제만보고 패턴을 찾아보거나 혹은 index를 하나씩 늘려가며 scan하면 되겠거니... 쉽게 생각했는데 소수점 이하의 자리수가 17자리 이상 나오지 않는다. 결국 검색해서 다른 사람이 풀이해 놓은 코드를 보고 구현...그냥 그대로 copy & paste 원리는 나머지가 반복되는 순간을 찾으면 순환마디.. 더보기
[오일러프로젝트] 25번문제 피보나치 수열은 아래와 같은 점화식으로 정의됩니다. Fn = Fn-1 + Fn-2 (단, F1 = 1, F2 = 1).이에 따라 수열을 12번째 항까지 차례대로 계산하면 다음과 같습니다. F1 = 1 F2 = 1 F3 = 2 F4 = 3 F5 = 5 F6 = 8 F7 = 13 F8 = 21 F9 = 34 F10 = 55 F11 = 89 F12 = 144수열의 값은 F12에서 처음으로 3자리가 됩니다. 피보나치 수열에서 값이 처음으로 1000자리가 되는 것은 몇번째 항입니까? 3개 언어 모두 간단히 swap이 제공되어서 로직을 비교적 쉽게 짤 수 있음. 재귀호출은 시간이 너무너무너무 오래걸려서 iteration 방식으로 작성 Python Ruby allen님의 ruby코드 Perl 더보기
[오일러프로젝트] 24번문제 어떤 대상을 순서에 따라 배열한 것을 순열이라고 합니다. 예를 들어 3124는 숫자 1, 2, 3, 4로 만들 수 있는 순열 중 하나입니다. 이렇게 만들 수 있는 모든 순열을 숫자나 문자 순으로 늘어놓은 것을 사전식(lexicographic) 순서라고 합니다. 0, 1, 2로 만들 수 있는 사전식 순열은 다음과 같습니다. 012 021 102 120 201 2100, 1, 2, 3, 4, 5, 6, 7, 8, 9로 만들 수 있는 사전식 순열에서 1,000,000번째는 무엇입니까? 예상했던대로 각 언어별로 라이브러리가 있어서 그냥 쉽게 접근하고 쉽게 풀었다. Python Ruby Perl Perl과 동일하게 Python이나 Ruby 모두 순서대로 출력하기 때문에 1000000번째에서 끊어도 동일한 결과가 .. 더보기
[오일러프로젝트] 23번문제 자신을 제외한 약수(진약수)를 모두 더하면 자기 자신이 되는 수를 완전수라고 합니다. 예를 들어 28은 1 + 2 + 4 + 7 + 14 = 28 이므로 완전수입니다. 또, 진약수의 합이 자신보다 작으면 부족수, 자신보다 클 때는 초과수라고 합니다. 12는 1 + 2 + 3 + 4 + 6 = 16 > 12 로서 초과수 중에서는 가장 작습니다. 따라서 초과수 두 개의 합으로 나타낼 수 있는 수 중 가장 작은 수는 24 (= 12 + 12) 입니다. 해석학적인 방법을 사용하면, 28123을 넘는 모든 정수는 두 초과수의 합으로 표현 가능함을 보일 수가 있습니다. 두 초과수의 합으로 나타낼 수 없는 가장 큰 수는 실제로는 이 한계값보다 작지만, 해석학적인 방법으로는 더 이상 이 한계값을 낮출 수 없다고 합니다.. 더보기

티스토리툴바