Project Euler42 [C/C++] 프로젝트 오일러 #59 : XOR 암호 풀기 이번 문제는 난이도가 5%이기는 하지만, 실제로 정석대로 푼다면 5%보다 높을 것 같네요. 암호를 푸는 방법은 무식한 방법으로 반복대치를 하는 경우가 많습니다. 단순 반복대치를 하면 풀 수는 있겠지만, 보통 수만대의 컴퓨터를 동원해도 몇천년, 몇만년 이상 걸리는 경우가 허다합니다. 양자컴퓨터가 나온다면 좀 달라질 수 있겠지만요. 이 문제에서는 주어진 텍스트에 3글자 소문자로 이루어진 키를 가지고 암호를 푸는 것입니다. 원래 문제 의도(난이도 5%)였다면, 3글자 소문자 키를 생성하고, 그것에 의해서 영어의 일반 언어가 도출되는지를 검사하면 되겠죠. 예를 들어서 a, this, is, are, you, 등등이 될겁니다. 전 고전적인 방법, 즉, 암호키를 알기 힘들다는 가정하에서 풀어보았습니다. .. 2016. 6. 16. [C++] 프로젝트 오일러 #58 : 나선형 소수들 #58 문제도 난이도는 5% 문제입니다. 문제 자체는 복잡해 보여도 사실 푸는데 전혀 어려움이 없는 문제예요. 문제는 1부터 차례대로 나선형으로 수들을 배치하게 되면, 대각선쪽에는 홀수가 항상 배치되게 됩니다. 그럴 경우, 대각선에 있는 홀수 중 소수의 비율이 얼마일것인가가 이 문제를 푸는데 중요한 부분입니다. 이 문제는 소수의 비율이 10% 미만으로 떨어질 때, 한 변에 위치하는 수들의 갯수를 답하라는 것입니다. 배치하는 방법이 일정하기 때문에, 대각선에 위치한 숫자들의 순열만 파악하면 됩니다. 일단 첫번째 대각선(가장 작은 수)의 수열은 다음과 같이 표현할 수 있습니다. s를 한변 길이의 절반이라고 할 때(즉, 1이 위치한 s는 0, 그 다음은 1, 그 다음은 2.. ), \[ f_s = 4s^.. 2016. 6. 15. [C++/Python] 프로젝트 오일러 #57 : 제곱근의 수렴 이번 문제는 수학 문제인 듯 보이지만, 그냥 단순 계산 문제입니다.프로젝트 오일러 사이트 난이도 평가 5% 문제네요. 문제의 내용은 2의 제곱근을 구할 때, 연분수 전개를 할 수가 있습니다. 연분수 전개에 관련해서는 펠의 방정식(http://sdev.tistory.com/213) 글을 참조하세요. 2=1+12+12+12+⋯=[1;2―] 와 같이 2의 제곱근을 표시할 수 있습니다. 이 문제에서는 이것이 중요한 것이 아니고, 이 연분수 전개를 할 때, 분수로 표현하게 되면, 분모와 분자가 모두 정수가 되는데, 분자의 정수부가 분보의 정수부보다 자릿수가 많은 것이 몇개가 있는 가가.. 2016. 6. 14. [C++/Python] 프로젝트 오일러 #56 : 제곱수의 자릿수 합 이 문제는 난이도 5% 문제이지만, BigInt 모듈이 없는 언어 사용자는 해당 모듈을 구해야 하는 어려움이 있습니다. 파이썬, 자바, C#과 같이 BigInt 모듈이 있는 프로그래밍 언어 등을 이용하면 간단하게 해결할 수 있습니다. 문제는 간단합니다.a, b 좀 더 좋은 알고리즘을 찾는다는 것은 어려울 것 같습니다. 그냥 무식한 방법으로 풀어보았습니다.프로그램의 관건은 C/C++에서는 Big Integer 라이브러리를 사용하거나, 간단한 형태로 Big Integer를 구현하면 됩니다.제 경우에는 직접 만들어 보았습니다. 아래는 제가 만든 소스입니다.//------------------------------------------------// Project Euler #56 - Powerf.. 2016. 6. 13. [C++/Python] 프로젝트 오일러 #55 라이크렐 수 이번 문제도 난이도 5% 문제입니다. 라이크렐 수는 어떤 양의 정수가 있다면, 그 정수를 10진수로 표현했을 때, 역순으로 표시된 수와의 합이 대칭수가 되는 가입니다. 대칭수가 되지 않으면, 마찬가지로 역순의 수와 더합니다. 이론상으로는 점점 증가하는 수이므로, 언젠가 확률적으로 대칭수(역순으로 표시해도 자기 자신이 되는 수)가 될 수 있습니다. 증명은 되지 않았지만, 무한히 시행해도 대칭수가 만들어지지 않는 수가 있다고 하고, 그 수들을 라이크렐 수라고 부릅니다. 그리고 그런 수중에 가장 작은 수가 196이라고 알려져 왔습니다. 문제는 얼마나 많이 시행을 하는 가에 따라서, 라이크렐 수라고 생각한 수가 라이크렐 수가 아닐 수도 있습니다. 그래서 이 문제에서는 시행횟수가 50번까지 안 되면 라이크.. 2016. 6. 10. [C/C++] 프로젝트 오일러 #54 : 포커 승리 판정 이번 문제는 어렵다는 생각은 들지 않았지만, 상당히 귀찮은 문제이긴 합니다.프로젝트 오일러 사이트에서의 난이도는 10% 문제입니다. 고포류 게임을 만들어본 적은 없지만, 포커의 룰에 따라서 누가 이겼는지를 판정하는 것은 포커 게임에서 가장 중요한 부분입니다. 그 외의 것이야 인터페이스이니까요. 이번 문제는 상당히 깁니다.최종적인 이야기는 결국 주어진 카드를 보고서 첫번째 사용자가 몇번 이겼는 가를 판정하는 것입니다.사실, 이런 판정시스템을 만드는 것이 단순히 노가다만은 아닙니다. 얼마나 더 효율적으로 판단할 수 있게 하는 것이 프로그램을 작성하는 사람에게는 고민이겠죠. 고포류 게임에서 노가다로 프로그램 짠다고 해서, 효율적 프로그램에 비해서 훨씬 더 느리다던지 하는 것은 아닙니다. 프로그램 코드.. 2016. 6. 10. 이전 1 2 3 4 5 6 7 다음 728x90
