프로젝트 오일러 #53 : 조합 선택
이번 문제는 간단한 문제입니다. 조합 공식만 알면 쉽게 문제를 풀 수 있습니다. n이 1부터 100까지 변할 때, 조합 숫자 \(_nC_r\)을 계산할 때, 1백만이 넘는 결과가 나오는 갯수를 적으면 됩니다.단순무식한 방법으로 하더라도, 총 10,100 번 조합 계산을 하면 됩니다. \(_nC_r = _nC_{n-r}\)이라는 사실을 알고 있다면, 그 절반으로 줄테고요. 대칭형인데, 단순증가 단순감소 패턴이라는 것을 아신다면, 더 횟수를 줄일 수 있습니다. 단, 조합을 계산하는 곱하기 횟수가 증가하니, 실제 곱하기 횟수로 따진다면, \(O(n^3)\)정도의 시간 복잡도를 가집니다. n이 100정도이니, 시간이 아주 조금 더 걸리는 것 뿐이지, 계산 못 할 정도는 절대 아닙니다. 저는, 조금 특이한 방법..
2016. 6. 9.
52. 프로젝트 오일러 #52 : 순열 곱
52번 문제는 너무나도 유명한 문제여서, 문제를 보고서 프로그램 작성을 하지 않고도 답을 낼 수 있었습니다. 이 문제는 순환소수 중, 소수에 의한 문제입니다. 문제 자체는 어렵지 않으니까, 어떻게든 풀면 됩니다. 난이도 5% 문제입니다. 51번 문제가 난이도 15%로 잠깐 높아졌었지만요. 프로젝트 오일러 사이트의 문제는 다음과 같습니다. 125874와 같은 숫자는 2배를 하면 251748로 숫자의 위치만 바뀌어서 나타납니다. x, 2x, 3x, 4x, 5x, 6x 가 모두 같은 숫자들을 가지고 있는 가장 작은 숫자를 찾으세요. 이 문제를 단순무식법으로 풀려면, 자릿수의 숫자만 계산해서 같은 숫자가 나오는지 검사하면 됩니다. 그렇지만, 그렇게 하면 시간이 많이 걸립니다. 사실 요즘 컴퓨터에서는 이렇게 하여..
2016. 6. 9.
51. 프로젝트 오일러 #51 : 소수 자릿수 대치
프로젝트 오일러 #51 문제는 처음으로 난이도 5%가 아닌 문제입니다. 다른 문제들에 비해서 난이도가 좀 있습니다. 주어진 문제는 56xx3 과 같은 x로 비어진 숫자가 있는데, 이 x에 0~9까지 숫자를 넣었을 때, 소수는 몇개가 나오는 가입니다. 56003, 56113, 56223, 56333, 56443, 56553, 56663, 56773, 56883, 56993 이라는 10개의 숫자들을 만들 수가 있는데요. 이 중 소수는 7개나 됩니다. 이 때, 56003(이 그룹 중 가장 작은 수)는 소수가 7개가 되는 최소의 수입니다. 찾아야 하는 수는 소수가 8개가 되는 최소의 수입니다. 문제를 적용하는 방법을 구상하는 것이 어렵지, 문제 자체는 짧은 시간에 컴퓨터가 계산해냈습니다. 저는 기본적으로 자기호..
2016. 6. 8.
49. 프로젝트 오일러 #49 : 소수 순열
이 문제는 좀 복잡해보이기는 하지만, 실제 풀이과정은 단순한 문제입니다. 세개의 4자리 숫자는 숫자들의 순서만 다르면서 소수인 숫자들입니다. 예를 들어서 1487, 4817, 8147 세 숫자는 1, 4, 7, 8 의 4개의 숫자들을 순서만 달리하면서, 각각이 소수인 숫자들입니다. 이러한 조건을 만족하는 또다른 숫자 조합을 찾으라는 것이 이 문제입니다. (실제 모든 경우를 해도, 4자리 숫자는 예를 든 것과 여기서 원하는 답, 이렇게 두가지밖에 없습니다.) 다음 그림은 프로젝트 오일러 사이트에 있는 문제입니다. 알고리즘을 작성할 때, 4자리로 만드는 순열을 어떻게 만들것인가가 가장 중요했습니다. 모든 경우를 다 찾아봐도 되겠지만, 그러면 경우의 수가 너무 많아집니다. 그래서 제 경우에는 4개의 숫자를 고..
2016. 6. 3.
