본문 바로가기
반응형

알고리즘 문제 & 프로그래밍/C++30

[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.
[C++]프로젝트 오일러 19번 문제&풀이 (20세기에서, 매월 1일이 일요일인 경우는 몇 번?) 문제 19번 다음은 달력에 관한 몇 가지 일반적인 정보입니다 (필요한 경우 좀 더 연구를 해 보셔도 좋습니다). 1900년 1월 1일은 월요일이다. 4월, 6월, 9월, 11월은 30일까지 있고, 1월, 3월, 5월, 7월, 8월, 10월, 12월은 31일까지 있다. 2월은 28일이지만, 윤년에는 29일까지 있다. 윤년은 연도를 4로 나누어 떨어지는 해를 말한다. 하지만 400으로 나누어 떨어지지 않는 매 100년째는 윤년이 아니며, 400으로 나누어 떨어지면 윤년이다 20세기 (1901년 1월 1일 ~ 2000년 12월 31일) 에서, 매월 1일이 일요일인 경우는 총 몇 번입니까? 접근방법 1. 매월 1일 & 일요일을 판명해야 하므로, (연 X 월)로 이루어진 2차원 배열을 만든다. 2. 1900년 1.. 2020. 12. 3.
[C++]프로젝트 오일러 18번 문제&풀이 (삼각형을 따라 내려가면서 합이 최대가 되는 경로 찾기) 문제 18번 다음과 같이 삼각형 모양으로 수를 배열했습니다. 3 7 4 2 4 6 8 5 9 3 삼각형의 꼭대기부터 아래쪽으로 인접한 수를 찾아 내려가면서 합을 구하면, 위의 그림처럼 3 + 7 + 4 + 9 = 23 이 가장 큰 합을 갖는 경로가 됩니다. 다음 삼각형에서 합이 최대가 되는 경로를 찾아서 그 합을 구하세요. 75 95 64 17 47 82 18 35 87 10 20 04 82 47 65 19 01 23 75 03 34 88 02 77 73 07 63 67 99 65 04 28 06 16 70 92 41 41 26 56 83 40 80 70 33 41 48 72 33 47 32 37 16 94 29 53 71 44 65 25 43 91 52 97 51 14 70 11 33 28 77 73 .. 2020. 12. 2.
반응형