53. 프로젝트 오일러 #53 : 조합 선택
이번 문제는 간단한 문제입니다. 조합 공식만 알면 쉽게 문제를 풀 수 있습니다. n이 1부터 100까지 변할 때, 조합 숫자 을 계산할 때, 1백만이 넘는 결과가 나오는 갯수를 적으면 됩니다. 단순무식한 방법으로 하더라도, 총 10,100 번 조합 계산을 하면 됩니다. 이라는 사실을 알고 있다면, 그 절반으로 줄테고요. 대칭형인데, 단순증가 단순감소 패턴이라는 것을 아신다면, 더 횟수를 줄일 수 있습니다. 단, 조합을 계산하는 곱하기 횟수가 증가하니, 실제 곱하기 횟수로 따진다면, 정도의 복잡도를 가집니다. 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.
