본문 바로가기
반응형

알고리즘 문제 & 프로그래밍40

[C++]프로젝트 오일러 12번 문제&풀이 (500개 이상의 약수를 갖는 가장 작은 삼각수는?) 문제 1부터 n까지의 자연수를 차례로 더하여 구해진 값을 삼각수라고 합니다. 예를 들어 7번째 삼각수는 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28이 됩니다. 이런 식으로 삼각수를 구해 나가면 다음과 같습니다. 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ... 이 삼각수들의 약수를 구해 봅시다. 1: 1 3: 1, 3 6: 1, 2, 3, 6 10: 1, 2, 5, 10 15: 1, 3, 5, 15 21: 1, 3, 7, 21 28: 1, 2, 4, 7, 14, 28 위에서 보듯이, 5개 이상의 약수를 갖는 첫번째 삼각수는 28입니다. 그러면 500개 이상의 약수를 갖는 가장 작은 삼각수는 얼마입니까? 접근방법(1차) - 코드는 맨 밑에! 1. 삼각수를 차례로 1부터 해.. 2020. 11. 23.
[C++]프로젝트 오일러 11번 문제&풀이 (20×20 격자에서 연속된 네 수의 곱 중 최댓값) 문제 아래와 같은 20×20 격자가 있습니다. 08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08 49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00 81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65 52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91 22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80 24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50 32 98 81 28 .. 2020. 11. 22.
[C++]프로젝트 오일러 10번 문제&풀이 (이백만 이하 소수의 합) 문제 10 이하의 소수를 모두 더하면 2 + 3 + 5 + 7 = 17 이 됩니다. 이백만(2,000,000) 이하 소수의 합은 얼마입니까? 접근방법(1차) - 코드는 맨 밑에! 1. 2부터 2,000,000까지 차례로 2. 1부터 해당 숫자까지로 나눠봐서, 나누어 지는 값이 2개이면 소수이므로 벡터에 저장하고, 3. 2보다 크면 그 숫자는 나누기를 중단한다. 4. 이렇게 저장된 벡터 요소의 합을 계산하면 끝 → 시간이 너무 오래 걸린다ㅠㅠ 개선사항 1. 2부터 2,000,000까지 모든 숫자를 나눠봐야 하므로 연산량이 많다. 2. 단순한 방법으로 하려 했지만 계산에 너무 많은 시간이 걸리므로, 에라토스테네스의 체를 사용하기로 결정! 접근방법(2차) 1. 에라토스테네스의 체를 사용! 2. 벡터에 숫자를 .. 2020. 11. 20.
[C++]프로젝트 오일러 9번 문제&풀이 (a + b + c = 1000 이 되는 피타고라스 수) 문제 세 자연수 a, b, c 가 피타고라스 정리 a2 + b2 = c2 를 만족하면 피타고라스 수라고 부릅니다 (여기서 a 2020. 11. 19.
[C++]프로젝트 오일러 8번 문제&풀이 (1000자리 수 안에서 이어지는 5개 숫자의 곱 중 최댓값은?) 문제 다음은 연속된 1000자리 수입니다 (읽기 좋게 50자리씩 잘라 놓음). 73167176531330624919225119674426574742355349194934 96983520312774506326239578318016984801869478851843 85861560789112949495459501737958331952853208805511 12540698747158523863050715693290963295227443043557 66896648950445244523161731856403098711121722383113 62229893423380308135336276614282806444486645238749 303589072962904915604407723907138105158593079608.. 2020. 11. 19.
[C++]프로젝트 오일러 6번 문제&풀이 (1부터 100까지 "제곱의 합"과 "합의 제곱"의 차는?) 문제 6번 1부터 10까지 자연수를 각각 제곱해 더하면 다음과 같습니다 (제곱의 합). 12 + 22 + ... + 102 = 385 1부터 10을 먼저 더한 다음에 그 결과를 제곱하면 다음과 같습니다 (합의 제곱). (1 + 2 + ... + 10)2 = 552 = 3025 따라서 1부터 10까지 자연수에 대해 "합의 제곱"과 "제곱의 합" 의 차이는 3025 - 385 = 2640 이 됩니다. 그러면 1부터 100까지 자연수에 대해 "합의 제곱"과 "제곱의 합"의 차이는 얼마입니까? 접근방법 1. 1부터 100까지 제곱의 합과 합의 제곱을 각각 구한다. 2. 구한 값의 차의 절대값이 우리가 구하고자 하는 값이다. (아무리 생각해도 쉬어가는 문제인 것 같다ㅎㅎ) #include #include usin.. 2020. 11. 19.
반응형

티스토리툴바