본문 바로가기
반응형

프로젝트오일러24

[C++]프로젝트 오일러 25번 문제&풀이 (피보나치 수열에서 처음으로 1000자리가 되는 항은 몇 번째?) 문제 25번 피보나치 수열은 아래와 같은 점화식으로 정의됩니다. Fn = Fn-1 + Fn-2 (단, F1 = 1, F2 = 1). 이에 따라 수열을 12번째 항까지 차례대로 계산하면 다음과 같습니다. F1 = 1 F2 = 1 F3 = 2 F4 = 3 F5 = 5 F6 = 8 F7 = 13 F8 = 21 F9 = 34 F10 = 55 F11 = 89 F12 = 144 수열의 값은 F12에서 처음으로 3자리가 됩니다. 피보나치 수열에서 값이 처음으로 1000자리가 되는 것은 몇번째 항입니까? 접근방법 1. 우선 numVec_1 벡터와 numVec_2 벡터에 1을 담고 이 두 벡터의 합이 numVec_3 벡터가 되도록 세팅한다. 2. 1000자리수까지 계산해야 하므로, numVec_3 벡터에 3자리씩 끊어서.. 2020. 12. 25.
[C++]프로젝트 오일러 24번 문제&풀이 (0, 1, 2, 3, 4, 5, 6, 7, 8, 9로 만들 수 있는 1,000,000번째 사전식 순열은?) 문제 24번 어떤 대상을 순서에 따라 배열한 것을 순열이라고 합니다. 예를 들어 3124는 숫자 1, 2, 3, 4로 만들 수 있는 순열 중 하나입니다. 이렇게 만들 수 있는 모든 순열을 숫자나 문자 순으로 늘어놓은 것을 사전식(lexicographic) 순서라고 합니다. 0, 1, 2로 만들 수 있는 사전식 순열은 다음과 같습니다. 012 021 102 120 201 210 0, 1, 2, 3, 4, 5, 6, 7, 8, 9로 만들 수 있는 사전식 순열에서 1,000,000번째는 무엇입니까? 접근방법 1. 팩토리얼 함수를 정의한다.(0! = 1 // n! = n * (n-1) * ... * 1) 2. numVec에 0~9까지의 숫자를 담고, 1000000번째의 숫자를 계산해보자. 3. 먼저 첫번째 올 .. 2020. 12. 22.
[C++]프로젝트 오일러 23번 문제&풀이 (두 과잉수의 합으로 나타낼 수 없는 모든 양의 정수의 합은?) 문제 23번 자신을 제외한 약수(진약수)를 모두 더하면 자기 자신이 되는 수를 완전수라고 합니다. 예를 들어 28은 1 + 2 + 4 + 7 + 14 = 28 이므로 완전수입니다. 또, 진약수의 합이 자신보다 작으면 부족수, 자신보다 클 때는 과잉수라고 합니다. 12는 1 + 2 + 3 + 4 + 6 = 16 > 12 로서 과잉수 중에서는 가장 작습니다. 따라서 과잉수 두 개의 합으로 나타낼 수 있는 수 중 가장 작은 수는 24 (= 12 + 12) 입니다. 해석학적인 방법을 사용하면, 28123을 넘는 모든 정수는 두 과잉수의 합으로 표현 가능함을 보일 수가 있습니다. 두 과잉수의 합으로 나타낼 수 없는 가장 큰 수는 실제로는 이 한계값보다 작지만, 해석학적인 방법으로는 더 이상 이 한계값을 낮출 수 .. 2020. 12. 11.
[C++]프로젝트 오일러 22번 문제&풀이 (영문 이름 점수 합계 구하기) 문제 22번 여기 5천개 이상의 영문 이름들이 들어있는 46KB짜리 텍스트 파일 names.txt 이 있습니다 (우클릭해서 다운로드 받으세요). 이제 각 이름에 대해서 아래와 같은 방법으로 점수를 매기고자 합니다. 먼저 모든 이름을 알파벳 순으로 정렬합니다. 각 이름에 대해서, 그 이름을 이루는 알파벳에 해당하는 수(A=1, B=2, ..., Z=26)를 모두 더합니다. 여기에 이 이름의 순번을 곱합니다. 예를 들어 "COLIN"의 경우, 알파벳에 해당하는 수는 3, 15, 12, 9, 14이므로 합이 53, 그리고 정렬했을 때 938번째에 오므로 최종 점수는 938 × 53 = 49714가 됩니다. names.txt에 들어있는 모든 이름의 점수를 계산해서 더하면 얼마입니까? 접근방법 1. 일단, 벡터(.. 2020. 12. 9.
[C++]프로젝트 오일러 21번 문제&풀이 (10000 이하 모든 친화수(우애수)의 합은?) 문제 21번 n의 약수들 중에서 자신을 제외한 것의 합을 d(n)으로 정의했을 때, 서로 다른 두 정수 a, b에 대하여 d(a) = b 이고 d(b) = a 이면 a, b는 친화쌍이라 하고 a와 b를 각각 친화수(우애수)라고 합니다. 예를 들어 220의 약수는 자신을 제외하면 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110 이므로 그 합은 d(220) = 284 입니다. 또 284의 약수는 자신을 제외하면 1, 2, 4, 71, 142 이므로 d(284) = 220 입니다. 따라서 220과 284는 친화쌍이 됩니다. 10000 이하의 친화수들을 모두 찾아서 그 합을 구하세요. 접근방법 1. 자신을 제외한 약수들의 합을 구하는 함수(calSum)를 만든다. (벡터(vec)에 약수들.. 2020. 12. 5.
[C++]프로젝트 오일러 20번 문제&풀이 (100! 의 자릿수를 모두 더하면?) 문제 20번 n! 이라는 표기법은 n × (n − 1) × ... × 3 × 2 × 1을 뜻합니다. 예를 들자면 10! = 10 × 9 × ... × 3 × 2 × 1 = 3628800 이 되는데, 여기서 10!의 각 자릿수를 더해 보면 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27 입니다. 100! 의 자릿수를 모두 더하면 얼마입니까? 접근방법 1. 파이썬으로 하면 간단하겠으나, C++는 자료형을 고려해서 풀어야 하기 때문에 조금 번거롭다. 2. 충분히 긴 벡터(numVector(200))를 만들고, 첫번째 자리에 1을 넣는다. 3. 벡터의 각 요소에 각 자리수가 들어가도록 할건데, 숫자를 그대로 넣고 10으로 나눠서 나머지는 남기고, 몫은 한칸씩 옆으로 보내 더해준다.(1의자리수가 numVe.. 2020. 12. 4.
반응형