반응형 프로젝트 오일러69 25. 프로젝트 오일러 #25 : 1000자리 피보나치 수열항 구하기 C/C++ 언어를 배우다보면, 꼭 한번은 프로그램해보는 것이 있다면, 피보나치 수열일거라 생각합니다. 피보나치 수열은 재귀함수를 사용한 곳에서도 많이 나오지만, 동적 프로그램이 필요한 예로도 자주 사용됩니다. 피보나치 수열은 한쌍의 토끼의 개체수 증가라는 퀴즈 형태에서 출발한 것인데요. 꼭 토끼가 아니라도 대장균의 증식같은 데에서도 응용할 수 있습니다. 기하함수로 증가하는 곡선을 보이게 됩니다. 피보나치는 아주 간단한 점화식을 이용합니다. 점화식을 보면 아주 간단한 형태입니다. 전항과 전전항을 더한 값이 현재항의 값이 됩니다. 그래서 첫번째 항과 두번째 항이 초기값으로 주어져야 합니다. 첫번째 항은 1, 두번째 항은 1입니다. 자연수 범위안에서 피보나치 수열은 진행합니다. 확장해서 음수항을 만들기도 하지.. 2015. 2. 17. 500. 프로젝트 오일러 #500 : 약수의 갯수가 2의 500500승인 최소수 찾기 이번 문제는 알고리즘이 관건인 문제인지라,일단 모든 수를 찾아서 가장 작은 수를 찾는 것은 쉽지 않습니다. 왜냐하면, 우리가 상상할 수 없을 정도로 큰 수가 나오니까요. 그리고 소인수분해를 하는 것도 쉽지 않죠. 소인수분해는 알고리즘 상 현재까지는 가장 진보된 알고리즘이라고 할 수 있는 것이 나와있지 않은 상태입니다. 소인수분해가 적절한 시간 (설사 며칠이 걸리더라도) 안에 풀 수 있다면, 지금의 공인 인증서를 비롯하여 많은 암호 체제가 모두 무용지물이 됩니다. 비대칭키 암호 알고리즘의 핵심은 소인수분해가 어렵다는 것을 토대로 하고 있습니다. 1000비트짜리 암호키를 가지는 비대칭키라고 한다면, 두개의 소수는 각각 500비트정도를 고르게 됩니다. 500비트라면, 10의 150승정도가 되죠. 즉, 그 근처.. 2015. 2. 7. 501. 프로젝트 오일러 #501 : 약수의 갯수가 8개인 수 찾기 그동안 프로젝트 오일러 문제를 1번부터 차례대로 풀다가, 좀 지겹다는 생각이 들더군요. 현재까지는 32개의 문제를 차례대로 풀어나갔는데요. 과연 뒤에 있는 문제들은 어떨까 생각이 들어서 찾아보았습니다. 뒤에 있는 문제는 도저히 일반적인 방법으로 풀지 못 하는 것들이네요.정답자도 십여명이고... 일단 도전하기로 했는데, 이 문제는 소수의 갯수를 알아야 풀 수 있는 문제인지라, 상당히 어렵네요. 숫자의 범위가 작으면 어떻게든 풀겠지만요. 앞에 있는 문제가 실제 프로그램 돌렸을 때, 1초 이내에 나온 것에 비해서, 이 문제는 며칠 이상이 걸릴 문제네요. 소수의 갯수는 숫자가 커지면, 그에 정비례는 아니지만, 꾸준하게 증가합니다. 약수의 갯수가 8개인 수들도 꾸준하게 증가하는데, 그 숫자의 증가속도가 좀 빠릅니.. 2015. 2. 6. 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. 이전 1 ··· 6 7 8 9 10 11 12 다음 728x90
