본문 바로가기
반응형

Programming/Project Euler112

58. 프로젝트 오일러 #58 : 나선형 소수들 #58 문제도 난이도는 5% 문제입니다. 문제 자체는 복잡해 보여도 사실 푸는데 전혀 어려움이 없는 문제예요. 문제는 1부터 차례대로 나선형으로 수들을 배치하게 되면, 대각선쪽에는 홀수가 항상 배치되게 됩니다. 그럴 경우, 대각선에 있는 홀수 중 소수의 비율이 얼마일것인가가 이 문제를 푸는데 중요한 부분입니다. 이 문제는 소수의 비율이 10% 미만으로 떨어질 때, 한 변에 위치하는 수들의 갯수를 답하라는 것입니다. 배치하는 방법이 일정하기 때문에, 대각선에 위치한 숫자들의 순열만 파악하면 됩니다. 일단 첫번째 대각선(가장 작은 수)의 수열은 다음과 같이 표현할 수 있습니다. s를 한변 길이의 절반이라고 할 때(즉, 1이 위치한 s는 0, 그 다음은 1, 그 다음은 2.. ), 이 것을 이용하여, 다음 수.. 2016. 6. 15.
57. 프로젝트 오일러 #57 : 제곱근의 수렴 이번 문제는 수학 문제인 듯 보이지만, 그냥 단순 계산 문제입니다.프로젝트 오일러 사이트 난이도 평가 5% 문제네요. 문제의 내용은 2의 제곱근을 구할 때, 연분수 전개를 할 수가 있습니다. 연분수 전개에 관련해서는 펠의 방정식(http://sdev.tistory.com/213) 글을 참조하세요. 와 같이 2의 제곱근을 표시할 수 있습니다. 이 문제에서는 이것이 중요한 것이 아니고, 이 연분수 전개를 할 때, 분수로 표현하게 되면, 분모와 분자가 모두 정수가 되는데, 분자의 정수부가 분보의 정수부보다 자릿수가 많은 것이 몇개가 있는 가가 문제입니다. 연분수 전개를 분수로 만들면 되는 것이지만, 연분수 전개 자체가 상당히 큰 자릿수가 나옵니다. 물론 double 형을 이용해서 근사치로 계산해도 되겠지만, .. 2016. 6. 14.
56. 프로젝트 오일러 #56 : 제곱수의 자릿수 합 이 문제는 난이도 5% 문제이지만, BigInt 모듈이 없는 언어 사용자는 해당 모듈을 구해야 하는 어려움이 있습니다. 파이썬 등을 이용하면 간단하게 해결할 수 있습니다. 문제는 간단합니다. a, b < 100 안에서 a의 b제곱한 결과를 10진수로 표현할 때, 모든 자릿수의 합 중 최대값을 찾으라는 것입니다. 최소값은 1인 것은 당연하고요. 좀 더 좋은 알고리즘을 찾는다는 것은 어려울 것 같습니다. 그냥 무식한 방법으로 풀어보았습니다. #include #include #include "NxBigInt.h" void solve1() { int v = 9, a, b; for( int i = 2 ; i < 100 ; i++ ) { NxBigInt m = i; for( int j = 2 ; j < 100 ; .. 2016. 6. 13.
프로젝트 오일러 #55 라이크렐 수 이번 문제도 난이도 5% 문제입니다. 라이크렐 수는 어떤 양의 정수가 있다면, 그 정수를 10진수로 표현했을 때, 역순으로 표시된 수와의 합이 대칭수가 되는 가입니다. 대칭수가 되지 않으면, 마찬가지로 역순의 수와 더합니다. 이론상으로는 점점 증가하는 수이므로, 언젠가 확률적으로 대칭수(역순으로 표시해도 자기 자신이 되는 수)가 될 수 있습니다. 증명은 되지 않았지만, 무한히 시행해도 대칭수가 만들어지지 않는 수가 있다고 하고, 그 수들을 라이크렐 수라고 부릅니다. 그리고 그런 수중에 가장 작은 수가 196이라고 알려져 왔습니다. 문제는 얼마나 많이 시행을 하는 가에 따라서, 라이크렐 수라고 생각한 수가 라이크렐 수가 아닐 수도 있습니다. 그래서 이 문제에서는 시행횟수가 50번까지 안 되면 라이크렐 수라.. 2016. 6. 10.
54. 프로젝트 오일러 #54 : 포커 승리 판정 이번 문제는 어렵다는 생각은 들지 않았지만, 상당히 귀찮은 문제이긴 합니다.프로젝트 오일러 사이트에서의 난이도는 10% 문제입니다. 고포류 게임을 만들어본 적은 없지만, 포커의 룰에 따라서 누가 이겼는지를 판정하는 것은 포커 게임에서 가장 중요한 부분입니다. 그 외의 것이야 인터페이스이니까요. 이번 문제는 상당히 깁니다.최종적인 이야기는 결국 주어진 카드를 보고서 첫번째 사용자가 몇번 이겼는 가를 판정하는 것입니다. 사실, 이런 판정시스템을 만드는 것이 단순히 노가다만은 아닙니다. 얼마나 더 효율적으로 판단할 수 있게 하는 것이 프로그램을 작성하는 사람에게는 고민이겠죠. 고포류 게임에서 노가다로 프로그램 짠다고 해서, 효율적 프로그램에 비해서 훨씬 더 느리다던지 하는 것은 아닙니다. 프로그램 코드 사이즈.. 2016. 6. 10.
프로젝트 오일러 #53 : 조합 선택 이번 문제는 간단한 문제입니다. 조합 공식만 알면 쉽게 문제를 풀 수 있습니다.  n이 1부터 100까지 변할 때, 조합 숫자 \(_nC_r\)을 계산할 때, 1백만이 넘는 결과가 나오는 갯수를 적으면 됩니다.단순무식한 방법으로 하더라도, 총 10,100 번 조합 계산을 하면 됩니다. \(_nC_r = _nC_{n-r}\)이라는 사실을 알고 있다면, 그 절반으로 줄테고요. 대칭형인데, 단순증가 단순감소 패턴이라는 것을 아신다면, 더 횟수를 줄일 수 있습니다. 단, 조합을 계산하는 곱하기 횟수가 증가하니, 실제 곱하기 횟수로 따진다면, \(O(n^3)\)정도의 시간 복잡도를 가집니다. n이 100정도이니, 시간이 아주 조금 더 걸리는 것 뿐이지, 계산 못 할 정도는 절대 아닙니다. 저는, 조금 특이한 방법.. 2016. 6. 9.
728x90

티스토리툴바