반응형 Programming/Project Euler89 [C/C++] 프로젝트 오일러 #72 분수 세기(수학) 이번 문제는 분수를 세는 문제입니다. 해당 문제는 아래 링크입니다. https://projecteuler.net/problem=72 Problem 72 - Project Euler Consider the fraction, n/d, where n and d are positive integers. If n projecteuler.net 이 문제는 분모의 범위가 정해졌을 때, 기약분수로 표현할 수 있는 분수는 총 몇개인가에 대한 문제입니다. 모든 경우를 다 따져서 기약분수로 만들어서 겹치는 것 제외하면 되겠다고 생각할 수 있지만, 이것이 생각처럼 쉽지 않습니다. \(d \leq 8\)인 분모 d를 갖는 기약분수는 다음과 같습니다. 1/8 3/8 5/8 7/8 1/7 2/7 3/7 4/7 5/7 6/7 1/6.. 2019. 12. 20. 프로젝트 오일러 #71 순서가 있는 분수 어려움 정도는 10%로 크게 어려움 없이 풀 수 있는 문제입니다. 분수문제가 연속으로 3문제가 나와있는데, 기약분수를 만드는 것만 잘 이해하면 풀 수 있는 문제들입니다. 아래는 이 문제의 원문이 있는 곳입니다. https://projecteuler.net/problem=71 Problem 71 - Project Euler Consider the fraction, n/d, where n and d are positive integers. If n projecteuler.net 분수를 표현하는 방법은 여러가지가 있을 수 있습니다. 그 중 유일한 표현법을 얻기 위해서 기약분수를 사용합니다. 기약분수로 표현을 할 때, 우리는 분수의 크기를 비교할 수 있죠. 그런데, 분모의 상한을 주게되면, 자연수를 나열하듯이 .. 2019. 11. 18. 프로젝트 오일러 #70 오일러의 수 순열 #69 문제와 비슷하게 이 문제도 오일러의 수를 다루고 있습니다. 난이도는 20%이네요. 문제 자체는 해석하는 데 있어서 어려움이 없습니다. n에 대한 오일러의 수가, n과 자릿수도 같고, 숫자의 조합도 같다면, 그 수는 순열수라고 할 수 있습니다. 이러한 순열수가 되는 10억 미만의 n 중에 그 비율이 최소가 되는, (즉, 상대적으로 오일러의 수가 크게 나오는) n을 찾으라는 것입니다. 이 문제를 #69와 같이 풀 수도 있겠지만요. 순열수가 되어야 한다는 조건 때문에, 일단 무식하게 프로그램을 짜보았습니다. 아쉽게도 무식하게 프로그램을 작성하면 시간이 많이 걸립니다. 전 12초정도 시간이 걸리네요. 순열수인지 아닌지는 9로 나눈 나머지가 동일한지 검사했습니다. 일단 그렇게 하면 많은 경우의 수가 줄어듭.. 2016. 9. 29. 프로젝트 오일러 #69 최대 오일러의 수 비율 이번 문제는 난이도 10%의 문제입니다. 사실 알고보면 어려운 문제는 아니지만, 오일러의 수라는 것에 대한 이해도가 없다면, 막막하게 느낄 수 있습니다. 오일러의 수는 어떤 수 n에 대하여, n보다 작을 자연수 중에, n과 서로소인 수의 갯수를 말합니다. 이 수는 암호학 등에서 아주 중요하게 다루어집니다. RSA와 같이 비대칭 키를 사용하는 암호학을 공부하고자 한다면, 오일러의 수를 이해하지 못 하면, 절대 해당 암호학을 이해할 수 없습니다. 대학에서 정수론이라는 과목을 들었다면 모를까, 그렇지 않다면, 배울 수 있는 기회는 별로 없죠. (요즘은 중학생들도 이것을 아는 애들이 있습니다. 수학 올림피아드에서 가끔씩 나오는 문제이다보니. 제 경우에는 정수론 책을 하나 사서 독학을 했습니다.) 문제에서는 n에.. 2016. 9. 27. 프로젝트 오일러 #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. 이전 1 2 3 4 5 6 ··· 15 다음 728x90
