Programming/Project Euler118 [C/C++] 프로젝트 오일러 #21 10,000 이하의 친화수 찾기. 이번 문제는 밀레니엄 문제급은 아니지만, 홀수 완전수가 존재하지 않는다의 증명과 같이 오랫동안 풀리지 않는 문제의 영역입니다. 완전수에 대해서 아시는 분들은 많을거라고 생각합니다. 완전수는 자신을 제외한 약수의 합이 자신이 되는 수를 뜻합니다. 대표적으로는 6, 28 과 같이 짝수만 존재합니다. 완전수의 갯수가 무한한가라는 것도 사실 밝혀진 바가 없습니다. 짝수 완전수의 경우에는 반드시 이 형태여야 된다는 것은 이미 증명되었고, 그 증명과정이 어렵지는 않습니다. 완전수와 비슷하게 친화수도 자기 자신을 제외한 약수의 합을 통해서 나타냅니다. 그 약수들의 합이 다른 수가 되고, 그 다른 수의 약수들의 합이 자신이 되면, 두 사이 관계는 친화수라고 합니다. 친화수가 수학에서 큰 비중을 가지는 수는 .. 2015. 1. 18. [C/C++] 프로젝트 오일러 #20 : 100!의 모든 자릿수 합 구하기 Factorial Digit Sum 문제는 주어진 수의 팩토리얼을 계산하고, 그 결과값에 포함된 모든 자릿수의 합을 구하는 문제입니다. 예를 들어, 10! (10 팩토리얼)은 10×9×8×⋯×1=3,628,800이고, 이 결과값의 자릿수 합은 3+6+2+8+8+0+0=27입니다. 문제에서는 100!의 결과값에 포함된 자릿수의 합을 구하라는 질문을 제시합니다. 이 문제는 매우 큰 수를 다루기 때문에 정수 연산과 효율적인 계산을 요구합니다. 알고리즘에서 가장 큰 알고리즘을 분류하는 것 중에, 기하급수보다 더 큰 것이 있다면, 모든 경우의 수를 조사하는 팩토리얼(factorial)일겁니다. 뭐 이것보다 .. 2015. 1. 17. [C/C++] 프로젝트 오일러 #19 : 20세기의 매달 1일이 일요일인 수 계산하기 이 문제는 윤년을 올바르게 찾을 수 있는가를 찾아내는 문제라고 생각합니다. C/C++ 에서는 time.h 헤더 파일에 있는 mktime() 함수를 이용하면 손쉽게 풀 수 있는 문제이기도 하죠. 그러나 저는 조금 다르게 찾아볼려고 노력을 했습니다. (mktime() 함수를 이용하면 윤초 계산도 들어가는지, y년 m월 1일 0시 0분 0초의 요일이 다르게 나오네요. 1시로 옮기니 정확하게 나옵니다.) 사람들에게 1년 주기는 어떤 기준인가를 물어보면, 올바르게 아는 사람들은 적습니다. 아마 많은 분들은 지구가 태양 주위를 한바퀴 도는데 걸리는 시간이라고 생각할겁니다. 아, 아니었나요? 반문하시는 분들도 계실 것 같네요. 정확하게는 춘분점에서 다음번 춘분점까지 걸리는 시간이 1년입니다. 지구가 태양을 .. 2015. 1. 17. [C/C++] 프로젝트 오일러 #18 : 삼각형 수들의 최대값 경로 구하기(동적 프로그래밍) 이번 프로그램은 개인적으로도 재미있을 것 같았습니다.Project Euler의 18번 문제는 삼각형 숫자 배열에서 위에서 아래로 내려오는 경로 중 합이 최대가 되는 경로를 찾는 문제입니다.문제에서 주어진 삼각형 숫자 배열에서 맨 위 숫자에서 시작하여 아래로 내려오면서 인접한 두 숫자 중 하나를 선택하여 이동합니다. 이때, 선택한 숫자들의 합이 최대가 되는 경로를 찾아 그 합을 구하는 것이 목표입니다.가장 중요한 알고리즘은 바로 동적 프로그래밍(Dynamic Programming)입니다. 실제 경로 문제 중 최적값 찾기에는 동적 프로그래밍 기법을 자주 사용하게 되는데, 이 프로그램 역시 마찬가지입니다.해당 사이트 문제에서도 그런 점을 언급하기는 했지만,동적 프로그래밍을 사용하지 않는다면, 경로의 수가 많.. 2015. 1. 14. [C/C++] 프로젝트 오일러 #17 : 영어 단어의 글자수 세기(구현) Project Euler 17번 문제는 1부터 1000까지의 모든 숫자를 영어 단어로 썼을 때 사용되는 글자의 총 개수를 구하는 문제입니다.예를 들어, 숫자 342는 "three hundred and forty-two"로 쓰고, 115는 "one hundred and fifteen"으로 씁니다. 이때 띄어쓰기나 하이픈('-')은 글자 수에 포함하지 않습니다.문제는 1부터 1000까지의 모든 숫자를 영어 단어로 썼을 때 사용되는 글자의 총 개수를 구하는 것입니다. 이번 문제는 문제 자체의 난이도보다는, 영어 단어를 세는 것 자체가 너무 짜증났던 문제입니다. 그리고 우리가 보통 사용하지 않는 'and'까지 쳐서 해주어야 하니까요. 답을 썼는데 계속 틀리다고 나와서, 왜 그런가 했더니, 제가 글자수 하나를 .. 2015. 1. 14. [C/C++] 프로젝트 오일러 #16 : 2의 1000승의 모든 자릿수 합 구하기(BigInteger) 사실 이번 프로그램은 Big integer를 사용할 줄 아느냐 아니냐에 따라서 달라진다고 봅니다.많은 언어가 기본으로 Big Integer를 지원하기 때문에, 언어에 따라서 구현 난이도도 차이가 많을겁니다. 문제에서 요구하는 것은 2의 1000제곱을 한 후, 모든 자리의 수를 합해서 결과를 내달라는 것입니다. 예를 들어서 python을 이용하면, 가볍게 이 문제를 해결할 수 있습니다. >>> 2**100010715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824.. 2015. 1. 13. 이전 1 ··· 14 15 16 17 18 19 20 다음 728x90
