본문 바로가기
반응형

Programming/Project Euler115

24. 프로젝트 오일러 #24 : 백만번째 순열 수 구하기 우리가 진법을 계산할 때, 과연 어떻게 할까요? 예를 들어서 723 을 8진법으로 계산한다면요? 이 계산을 위해서 우리는 나누기 연산을 계속 하게 됩니다. 중학교 수학을 들추어 보면 보통 다음과 같이 계산을 합니다. 으로 723은 8진수로 으로 표시가 됩니다. 이것을 수식으로 표현하면 다음과 같이 표현할 수 있습니다. 이야기는 우리는 8의 3승부터 차례로 나누어 나가서 몫만 챙겨도 똑같이 위와 같은 결론에 도달할 수 있다는 것을 의미합니다. 그런데, 순열은 다른 것이 아닌가요? 순열은 한번 사용된 글자는 사용할 수 없다는 것만 빼고는 위와 같습니다. 그런 이유 때문에, 진법계산을 할 때, 1의 자릿수부터 계산하는 것이 가능한 반면, 순열은 그렇지 못 합니다. 반드시 가장 큰 자리부터 계산해야 합니다. 예.. 2015. 1. 27.
23. 프로젝트 오일러 #23 : 초과수의 합으로 표현 안되는 자연수들의 합 이번 문제는 약수들의 합을 구하는 기존 문제들과 크게 다를 바가 없습니다. 약수들의 합을 보통은 σ(n)으로 표현을 하는데요. 이 중, 자기자신을 뺀 약수들의 합을 가지고, 자기자신과 적으면 부족수, 같으면 완전수, 크면 초과수라고 합니다. 초과수는 무한하게 많이 생길 수밖에 없는데요. 실제 증명에 의하면, 초과수의 분포가 숫자 범위가 커지면서 크게 늘어나지도 않고, 줄어들지도 않는다고 합니다. 초과수는 다음과 같은 경우가 있습니다. 1. 완전수의 배수들(당연히 자신들은 빼야합니다.) 2. 초과수의 배수들(초과수 자신들은 포함됩니다.) 초과수가 되기 위해서는 작은 소수들로 이루어진 숫자들이 필요합니다. 초과수 중에 가장 작은 수는 12인데요. 사실 12는 완전수 6의 배수입니다. 완전수는 다음과 같이 표.. 2015. 1. 26.
22. 프로젝트 오일러 #22 : 이름 점수 구하기 이번 문제는 이름 점수를 구해서 정렬한 순서값을 곱하는 비교적 간단한 알고리즘입니다. 정렬이야 원래 C/C++ 에 들어가 있는 qsort()를 써도 되고, 아주 간단한 알고리즘을 적용해도 그다지 큰 문제가 없습니다. 저는 힙정렬을 만들어서 짜보았습니다. 힙정렬이 베스트라고는 할 수는 없지만, 처음에는 파일로 읽어서 사용할 예정이었기 때문에, 힙정렬이나 삽입정렬이 그런면에서는 유리한 점이 있습니다. 다른 정렬은 모두 배열에 일단 넣고, 그 다음 정렬을 하게 되지만, 힙정렬이나 삽입정렬은 삽입을 비교적 다른 정렬 방법에 비해서 손쉽게 할 수 있는 장점이 있습니다. 정렬 과정에서 삽입과정이 일어나니까요. 주어진 데이터 파일을 보니, 파싱보다는 그냥 소스에 붙여넣기 또는 #include "names.txt"를 .. 2015. 1. 25.
[C/C++] 프로젝트 오일러 #21 10,000 이하의 친화수 찾기. 이번 문제는 밀레니엄 문제급은 아니지만, 홀수 완전수가 존재하지 않는다의 증명과 같이 오랫동안 풀리지 않는 문제의 영역입니다. 완전수에 대해서 아시는 분들은 많을거라고 생각합니다. 완전수는 자신을 제외한 약수의 합이 자신이 되는 수를 뜻합니다. 대표적으로는 6, 28 과 같이 짝수만 존재합니다. 완전수의 갯수가 무한한가라는 것도 사실 밝혀진 바가 없습니다. 짝수 완전수의 경우에는 반드시 이 형태여야 된다는 것은 이미 증명되었고, 그 증명과정이 어렵지는 않습니다. 완전수와 비슷하게 친화수도 자기 자신을 제외한 약수의 합을 통해서 나타냅니다. 그 약수들의 합이 다른 수가 되고, 그 다른 수의 약수들의 합이 자신이 되면, 두 사이 관계는 친화수라고 합니다. 친화수가 수학에서 큰 비중을 가지는 수는 아닙니다. .. 2015. 1. 18.
20. 프로젝트 오일러 #20 : 100!의 모든 자릿수 합 구하기 알고리즘에서 가장 큰 알고리즘을 분류하는 것 중에, 기하급수보다 더 큰 것이 있다면, 모든 경우의 수를 조사하는 팩토리얼(factorial)일겁니다. 뭐 이것보다 더 큰 것도 있을 수 있는데요. 예를 들면, 연제곱승(제곱승에 제곱승이 이어나가는)이 있지만, 이런 알고리즘은 거의 보기 힘듭니다. 연제곱승과 반대되는 것으로는 연로그(로그 안에 로그가 있는 형태)이거나, 연로그가 일정한 값이 되는 로그의 갯수 등입니다. 정확한 용어는 제가 모르지만, 힙정렬에서 힙을 만드는 과정에 이런 개념이 나옵니다. 사실 정렬에서 우리는 일반적으로 이라고 알고 있지만요. 사실 더 본격적으로 들어가면, n개가 배열될 수 있는 경우의 수를 매번 2가지 경우로 나누어져서 찾아서 정렬하는 방법이기 때문에, 최적의 정렬 알고리즘의 .. 2015. 1. 17.
19. 프로젝트 오일러 #19 : 20세기의 매달 1일이 일요일인 수 계산하기 이 문제는 윤년을 올바르게 찾을 수 있는가를 찾아내는 문제라고 생각합니다. C/C++ 에서는 time.h 헤더 파일에 있는 mktime() 함수를 이용하면 손쉽게 풀 수 있는 문제이기도 하죠. 그러나 저는 조금 다르게 찾아볼려고 노력을 했습니다. (mktime() 함수를 이용하면 윤초 계산도 들어가는지, y년 m월 1일 0시 0분 0초의 요일이 다르게 나오네요. 1시로 옮기니 정확하게 나옵니다.) 사람들에게 1년 주기는 어떤 기준인가를 물어보면, 올바르게 아는 사람들은 적습니다. 아마 많은 분들은 지구가 태양 주위를 한바퀴 도는데 걸리는 시간이라고 생각할겁니다. 아, 아니었나요? 반문하시는 분들도 계실 것 같네요. 정확하게는 춘분점에서 다음번 춘분점까지 걸리는 시간이 1년입니다. 지구가 태양을 한바퀴 돌.. 2015. 1. 17.
728x90

티스토리툴바