프로젝트 오일러 #60 소수쌍 집합
이번 문제는 처음으로 난이도 20%짜리 문제입니다. 소수쌍이라고 해서 특별한 수학적인 내용이 들어가 있는 것은 아닙니다. 3, 7 이 두개의 소수가 있다고 하면, 이 두개의 소수를 단순하게 이어서 37, 73을 만들었을 때, 이 수들도 소수가 되면, (3, 7)은 소수쌍이 되는 것입니다. 이러한 소수들은 무한히 존재하겠지만, 빈도가 많지는 않습니다. 이 문제를 풀기 위해서는 메모리를 사용해서 해당되는 셋들을 만들것인가가 중요했습니다. 그렇게 하려면, 너무 자료구조가 복잡해서, 약간의 꼼수를 사용했습니다. 일단, 소수들을 결합하기 위한 재료는 미리 저장을 해놓고, 소수들을 결합한 결과에 대한 소수 검사는 별도의 라이브러리를 이용했습니다. 그리고 min이라는 정적 변수를 두어서, 이 값을 이용해서 현재 구해..
2016. 6. 17.
59. 프로젝트 오일러 #59 : XOR 암호 풀기
이번 문제는 난이도가 5%이기는 하지만, 실제로 정석대로 푼다면 5%보다 높을 것 같네요. 암호를 푸는 방법은 무식한 방법으로 반복대치를 하는 경우가 많습니다. 단순 반복대치를 하면 풀 수는 있겠지만, 보통 수만대의 컴퓨터를 동원해도 몇천년, 몇만년 이상 걸리는 경우가 허다합니다. 양자컴퓨터가 나온다면 좀 달라질 수 있겠지만요. 이 문제에서는 주어진 텍스트에 3글자 소문자로 이루어진 키를 가지고 암호를 푸는 것입니다. 원래 문제 의도(난이도 5%)였다면, 3글자 소문자 키를 생성하고, 그것에 의해서 영어의 일반 언어가 도출되는지를 검사하면 되겠죠. 예를 들어서 a, this, is, are, you, 등등이 될겁니다. 전 고전적인 방법, 즉, 암호키를 알기 힘들다는 가정하에서 풀어보았습니다. 물론 암호키..
2016. 6. 16.