콘텐츠로 건너뛰기
Home » 스터디 » Project Euler » 페이지 2

Project Euler

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

오일러 프로젝트 75

문제

긴 철사를 구부려서 세 변이 정수인 직각 삼각형을 만들 때, 그 방법이 한 가지 뿐인 경우는 12cm를 최소로 해서 아래와 같이 여러 개가 있습니다. 

12cm: (3, 4, 5)
24cm: (6, 8, 10)
30cm: (5, 12, 13)
36cm: (9, 12, 15)
40cm: (8. 15, 17)
48cm: (12, 16, 20)

반면에, 20cm의 경우 처럼 세 변이 정수인 직각 삼각형을 만들 수 없을 때도 있고, 여러 종류의 직각 삼각형을 만들 수 있을 때도 있습니다. 예를 들어 120cm의 철사로는 세 가지의 서로 다른 직각 삼각형이 만들어집니다. 

120cm: (30, 40, 50), (20, 48, 52), (24, 45, 51)

그러면 길이가 백오십만(1,500,000)이하인 철사를 가지고 세 변이 정수인 직각삼각형을 만들 때, 그 길이로는 한가지 방법으로만 만들 수 있게 되는 경우는 모두 얼마나 됩니까?

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

오일러 프로젝트 72

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

더 보기 »오일러 프로젝트 72
페이지 1 2

프로젝트 오일러 69

오일러의 피(phi)함수 φ(n)은 n보다 작거나 같으면서 n과 서로 소인 숫자의 개수를 나타냅니다. 예를 들어, 9보다 작거나 같으면서 9와 서로 소인 것은 1, 2, 4, 5, 7, 8이므로 φ(9)=6이 됩니다. n 서로 소인 수 φ(n) n/φ(n) 2 1 1 2 3 1, 2 2 1.5 4 1, 3 2 2 5 1, 2, 3, 4 4 1.25 6 1, 5 2 3 7 1, 2, 3, 4, 5, 6 6 1.1666… 8 1, 3, 5, 7 4 2 9 1, 2, 4, 5,… 더 보기 »프로젝트 오일러 69

오일러 프로젝트 70

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

오일러 프로젝트 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