Home » 스터디 » Project Euler » Page 2

Project Euler

오일러 프로젝트의 문제 풀이. 주로 파이썬과 Swift로 풀이합니다. (Python 3.6, Swift 4.0)

오일러 프로젝트 72

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

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

프로젝트 오일러 69

69번 풀이를 빼먹고 70번을 넘어갔었다. 69번 문제는 오일러 피 함수에 관한 문제인데, 문제를 주의깊게 읽어보면 사실 피 함수를 작성하는 것이 목적이 아니다. 오일러의 피(phi)함수 φ(n)은 n보다 작거나 같으면서 n과 서로 소인 숫자의 개수를 나타냅니다. 예를 들어, 9보다 작거나 같으면서 9와 서로 소인 것은 1, 2, 4, 5, 7, 8이므로 φ(9)=6이 됩니다. 위에서 보듯이 n ≤ 10인 경우 n/φ(n)의 값은 n=6일때 최대가 됩니다. n이 1,000,000 이하의 자연수일 때, n/φ(n)는 언제 최대가 됩니까? n 서로 소인 수 φ(n) n/φ(n) 2 1 1 2 3 1, 2 2 1.5 4… 더 보기 »프로젝트 오일러 69

오일러 프로젝트 70

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

오일러 프로젝트 68

오일러 프로젝트 68 번은 특별한 마방진에 관한 문제이다. 문제에 그림이 등장하기 때문인지 (한국어 사이트 기준으로) 풀이 수도 많지 않고, 포럼에 등록된 답변도 많지 않지만, 문제의 조건을 유심히 살펴보면 시험해야 하는 경우의 수를 많이 줄일 수 있고, 코드의 실행 시간 역시 그리 길지 않은 평이한 난이도를 가지고 있다.
더 보기 »오일러 프로젝트 68

오일러 프로젝트 67

오일러 프로젝트 67번 문제는 18번 문제와 동일하나 주어지는 데이터의 양이 훨씬 크다. 18번 문제의 경우에는 모든 경로를 계산하는 것이 불가능한 수준은 아니었으나, 이 문제의 가능한 모든 경로는 2^99 가지나 된다. 하지만 우리는 이미 18번 문제를 동적 계획법에 따라 풀어보았고, 이 문제 역시 같은 방식으로 풀어 낼 수 있다.

더 보기 »오일러 프로젝트 67

오일러 프로젝트 66

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

Pages: 1 2

오일러 프로젝트 64

오일러 프로젝트 64 번 문제는 자연수의 제곱근을 연분수로 전개할 때, 반복되는 패턴을 찾는 문제이다. 이는 자연수의 제곱근을 연분수로 전개해서 풀어 쓰는 과정을 추적하여, 연분수식 모양내에서의 각 위치의 항의 계수간의 점화식을 찾는 것으로 출발할 수 있다.
더 보기 »오일러 프로젝트 64

오일러 프로젝트 62

오일러 프로젝트 62 번 문제는 순열로 이루어진 숫자들 사이에서 세 제곱수가 5번 나오는 수를 찾는 것이다.  60번을 넘어서면서부터는 한국어 사이트의 포럼에서 정답자 수나 코드를 올린 포스트의 수가 격감하는데, 이 문제는 그리 어려운 수준의 문제는 아니다.
더 보기 »오일러 프로젝트 62