콘텐츠로 건너뛰기
Home » 오일러 프로젝트

오일러 프로젝트

오일러 프로젝트 80

자연수의 제곱근이 정수가 아니라면 무리수가 되고, 이런 경우 소수점 밑으로 반복되는 패턴이 전혀 없는 숫자들이 무한히 전개됩니다.2의 제곱근은 1.41421356237309504880… 인데, 처음 100개까지의 자릿수를 모두 더하면 475입니다. 1부터 100까지의 자연수 중에서 제곱근이 무리수인 경우에 대해, 처음 100개까지의 자릿수를 더한 값들의 총합은 얼마입니까? 접근 파이썬에서 제곱근을 구하는 방법은 math.sqrt() 함수를 사용할 수도 있고, n ** 0.5를 사용하는 방법이 있다. 그런데 이 두 경우에 연산 결과는 float 타입으로 정밀도가 제한된 부동소수점 숫자 타입을 사용하기 때문에 소수점 아래 99자리까지의 실제 숫자를 알 수 없다.… 더 보기 »오일러 프로젝트 80

오일러 프로젝트 72

오일러 프로젝트 72 번 문제는 여태껏 나왔던 문제에서의 최고 난이도를 또 한 번 갱신했다. 오일러 피 함수(\phi )의 1에서 100만까지의 자연수에 대한 피함수 값의 합을 구해야하는 문제이며, 피 함수를 빠르게 작성하는 것이 얼마나 고된(?)일인지 알고 있다면 이 문제를 brute force로 푸는 것은 정말 답이 없다는 점에서 마음을 단단히 먹어야 한다.

더 보기 »오일러 프로젝트 72
Pages: 1 2

오일러 프로젝트 70

어느덧 오일러 프로젝트 풀이를 포스팅한게 70번째에 다다랐다. 점점 강려크한 난이도의 문제들이 나오면서 한 회 한 회 포스팅이 정말 쉽지 않다. 오일러 프로젝트 70 번 문제도 오일러 피(phi) 함수에 대한 내용이다. 이번에는 피함수의 값이 원래 값과 순열이 되는 조금 특별한 케이스를 찾는 문제이다.
더 보기 »오일러 프로젝트 70

오일러 프로젝트 69

오일러 프로젝트 69 번 문제는 오일러의 피(phi)함수에 관한 내용이다. 사실 소인수분해를 빠르게 할 수 있는 방법만 있다면, 오일러 피함수 역시 간단하게 구현할 수 있으나, 여기서는 범위가 1,000,000까지이므로 만만한 문제가 아닐 수 있다. 그런데 문제를 잘 파악해보면 의외로 쉬운 문제이기도 하다.
더 보기 »오일러 프로젝트 69

오일러 프로젝트 68

아래와 같이 바방진과 유사한 성질을 가진 도형이 있습니다. 1부터 6까지의 숫자가 한 번씩만 사용되었고, 선을 따라 합을 구하면 항상 9가 됩니다.

바깥으로 뻗친 가지 중에서 가장 숫자가 낮은 것부터 시작해서 직선들을 시계 방향으로 돌아가며 나열하면, 도형의 모양을 숫자로 나타낼 수 있습니다. 위 그림의 예를 들면 4,3,2; 6,2,1; 5,1,3 이 됩니다.

위 도형으로는 네 가지 다른 합계를 가지도록 배열할 수 있는데, 다음과 같은 여덟개의 풀이가 존재합니다.

  • 합계 9 : 4,2,3; 5,3,1; 6,1,2
  • 합계 9 : 4,3,2; 6,2,1; 5,1,3
  • 합계 10 : 2,3,5; 4,5,1; 6,1,3
  • 합계 10 : 2,5,3; 6,3,1; 4,1,5
  • 합계 11 : 1,4,6; 3,6,2; 5,2,4
  • 합계 11 : 1,6,4; 5,4,2; 3,2,6
  • 합계 12 : 1,5,6; 2,6,4; 3,4,5
  • 합계 12 : 1,6,5; 3,5,4; 2,4,6

하나의 풀이에 대해서 각 숫자를 모두 이어 붙이면 9자리의 숫자를 만들 수 있고, 그 중에서 가장 큰 것은 432621513이 됩니다.
이제 아래와 같은 도형에다 마방진의 성질을 가지도록 1부터 10까지의 숫자를 채우고, 같은 방식으로 풀이 숫자를 이어붙이면 16자리 혹은 17자리의 숫자가 만들어집니다. 이 때, 16자리 숫자 중에서 가장 큰 것은 무엇입니까?

https://euler.synap.co.kr/problem=68
더 보기 »오일러 프로젝트 68

오일러 프로젝트 67

아래와 같은 삼각형의 꼭대기에서 인접한 수를 따라 내려가는 경로의 합을 계산해보면, 붉은 색으로 표시한 경우가 3 + 7 + 4 + 9 = 23 으로 가장 큽니다.

텍스트 파일 triangle.txt에는 100줄짜리 삼각형 수 데이터가 들어있습니다. 꼭대기에서 바닥에 이르는 경로의 합 중 최댓값은 얼마입니까?

참고: 이 문제는 18번 문제와 비슷하지만 훨씬 더 어려운 버전입니다. 이 문제를 풀려고 모든 경로를 계산하는 것은 가능하지 않은데, 경우의 수가 모두 299나 되기 때문입니다. 일 초에 1조(1012)개의 경로를 계산할 수 있다고 해도, 모든 경우의 수를 계산하려면 200억년이 걸립니다. 이 문제를 해결할 수 있는 효율적인 알고리듬을 찾아보시기 바랍니다.

https://euler.synap.co.kr/problem=67
더 보기 »오일러 프로젝트 67

오일러 프로젝트 66

오일러 프로젝트 66번 문제는 펠 방정식의 최소해에 관한 문제이다. 나이브하게 접근했다가는 결코 풀어낼 수 없을 수준으로 시간이 많이 걸린다. 그리고 그나마 빠른 해법 역시 구현하기 위해 여러 가지 지식과 스킬이 동원된다.  접근 방법을 알고 있더라도 구현이 만만치 않은, 1번부터 현재까지는 최고 난이도의 문제라 할 수 있다. 통상 오일러 프로젝트의 문제들은 순서에 맞게 풀어나갈 필요는 없지만, 이 문제 만큼은 57번, 64번, 65번을 풀 때의 지식이 그대로 요구된다.
더 보기 »오일러 프로젝트 66

Pages: 1 2