본문 바로가기
반응형

프로젝트 오일러69

프로젝트 오일러 #68 매직 오각 링 이 문제는 난이도 25%로 앞에 나열된 문제들에 비해서는 높은 편입니다. 매직 오각 링이라는 도형이 들어가는데, 이 도형만 잘 이해가 된다면 어려운 문제까지는 아닙니다. 위 그림은 매직 삼각 링입니다. 매직 삼각 링은 6개의 숫자가 있는데, 여기에 1 부터 6까지의 숫자를 채워넣게 됩니다. 그런데 여기에는 규칙이 있습니다. 일직선상의 세개 숫자의 합이 모두 같아야 합니다. 위 그림에서는 각 숫자들의 합이 9로 동일합니다. 이 그림이 매직 오각 링이며, 여기서 구해야할 문제입니다. 이 매직 오각 링에 들어갈 숫자는 1 부터 10까지의 숫자입니다. 이 숫자들을 세개의 숫자씩 시계방향으로 쭉 나열하면 총 15개의 숫자가 나옵니다. 그런데 10이란 숫자가 있으니까, 이 숫자들을 모두 붙이면, 16자리 또는 17.. 2016. 7. 4.
프로젝트 오일러 #67 최대 경로의 합 난이도는 5%로 별로 높지 않은 문제입니다. 그러나 A* 알고리즘 등 기초 알고리즘을 이용해서 짤 수 있는 문제이고, 또, 많은 게임 프로그램에서 활용 가능한 문제입니다. Maximum path sum II 어떤 한 곳에서 갈 수 있는 길은 2가지이므로, 높이가 10이면, 2의 9승인 512가지의 길이 존재합니다. 이 길 중 상당부분은 부분경로가 같기 때문에, 이러한 경로의 합을 구하는 방법으로는 동적프로그래밍(dynamic programming)이라는 알고리즘 기법을 이용해서 풀면 좋습니다. 동적 프로그래밍은 메모리를 추가로 사용해야 하지만, 저는 그냥 기존의 데이터 저장공간을 그대로 사용했습니다. 그렇게 하여도 큰 문제가 없겠죠. 중간에 한 지점에 대해서 올 수 있는 경로는 최대 2가지입니다. 그 2.. 2016. 6. 30.
프로젝트 오일러 #66 디오판투스 수식 이번 문제는 난이도 25% 문제이지만, 수학적인 부분을 모르면 매우 어렵습니다. 그냥 수식만 따라가서 풀려면, 풀기 힘든 문제예요. https://projecteuler.net/problem=66 Problem 66 - Project Euler Consider quadratic Diophantine equations of the form: x2 – Dy2 = 1 For example, when D=13, the minimal solution in x is 6492 – 13×1802 = 1. It can be assumed that there are no solutions in positive integers when D is square. By finding minimal solutions in proj.. 2016. 6. 29.
프로젝트 오일러 #64 홀수 주기의 제곱근 프로젝트 오일러 #64 는 연분수로 제곱근을 표현하는 문제입니다. 문제의 난이도는 20%입니다. 알고리즘적으로 어려운 것보다는 수학적 개념의 어려움이 있었던 문제라고 봅니다. 제곱근을 연분수로 표현하는 문제는 #57번(http://sdev.tistory.com/237)에 이미 나왔었습니다. 문제의 링크는 아래와 같습니다. https://projecteuler.net/problem=64 연분수로 표현할 때, 중요한 점은 분자는 항상 1이 되어야 한다는 것입니다. 예를 들어서 7의 제곱근인 \( sqrt{7} \)은 다음과 같이 표현할 수 있습니다. \[ \sqrt{7} = 2 + \sqrt{7} - 2 \] 위 식은 너무나도 당연한 것이겠지만요. 우리는 이것을 이용해서 연분수를 만들 수가 있습니다. 일단 .. 2016. 6. 22.
프로젝트 오일러 #63 제곱수의 자릿수 세기 제곱수 문제이긴 하지만, 의외로 이 문제는 쉽습니다. 난이도도 5%입니다. 문제는 n자리의 수중에 어떤 수의 n제곱이 되는 수가 몇개나 존재할까입니다. 예를 들어서 \(16807=7^5\) 인데, 16807은 5자리의 수이고 7의 5제곱이 되는 수죠. 이 문제의 링크는 아래에 있습니다. https://projecteuler.net/problem=63 Problem 63 - Project Euler The 5-digit number, 16807=75, is also a fifth power. Similarly, the 9-digit number, 134217728=89, is a ninth power. How many n-digit positive integers exist which are also an.. 2016. 6. 21.
프로젝트 오일러 #62 세제곱수 순열 이번 문제는 난이도 15% 문제네요. 저는 의외로 쉽게 풀었습니다. (단순무식법으로요.) 서로 다른 세제곱수 5개가 같은 숫자들로 이루어진 경우 그 중 가장 작은 수를 구하라는 문제입니다. 사실 이 문제를 정석적으로 푼다면, 정확하게 5개가 나오는지 검사해야 하지만, 저는 그것까지는 검사하지 않았습니다. 또한 같은 숫자가 4개 이상 나오는 것도 배제했습니다. 사실 그러면 안 되지만, 배열에다가 데이터를 저장하는 방식을 이용하다보니, 같은 숫자가 4개 이상 나오면 안 되어서요. 해시를 쓰면 좀 더 나으려나요. 그러면 자릿수가 6자리인것, 7자리인것, .. 형태로 정확하게 5개가 나오면서, 같은 숫자가 4개 이상 나오는 것도 허용할 수 있었을텐데요. 그치만 복잡한 자료구조 쓰는 것을 귀찮아해서요. (아무래도.. 2016. 6. 20.
728x90