🗒️ Problem Solving/Project Euler (17)

1. 2021.01.04 [Project Euler #17][C++] 1부터 1000까지 영어로 썼을 때 사용된 글자의 개수는?

   문제17 : 1부터 1000까지 영어로 썼을 때 사용된 글자의 개수는? 문제 1부터 5까지의 수를 영어로 쓰면 one, two, three, four, five 이고, 각 단어의 길이를 더하면 3 + 3 + 5 + 4 + 4 = 19 이므로 사용된 글자는 모두 19개입니다. 1부터 1,000까지 영어로 썼을 때는 모두 몇 개의 글자를 사용해야 할까요? 참고: 빈 칸이나 하이픈('-')은 셈에서 제외하며, 단어 사이의 and 는 셈에 넣습니다. 예를 들어 342를 영어로 쓰면 three hundred and forty-two 가 되어서 23 글자, 115 = one hundred and fifteen 의 경우에는 20 글자가 됩니다. 문제 해결 방법 100 이상의 수의 경우, 100으로 나누어 떨어지는 수..
2. 2020.12.31 [Project Euler #16][C++] $2^{1000}$ 의 각 자릿수를 모두 더하면?

   문제16 : $2^{1000}$ 의 각 자릿수를 모두 더하면? 문제 $2^{15} = 32768$ 의 각 자릿수를 더하면 3 + 2 + 7 + 6 + 8 = 26 입니다. $2^{1000}$ 의 각 자릿수를 모두 더하면 얼마입니까? 문제 해결 방법 2^{1000}21000 은 너무나 큰 수이기에 C++ 의 정수형 변수에 대입할 수 없다. 그래서 string 자료형을 이용하여 문제를 해결하였다.내용 참고 : click참고char형 숫자 -> int형 숫자 : char형 숫자 - '0'int형 숫자 -> char형 숫자 : int형 숫자 + '0' 소스 코드 정답 1366 심화 공부 숫자의 거듭제곱 계산(Computing Powers of a Number) x를 nn번 곱한 수를 x^nxn이라 한다. 현재의..
3. 2020.12.28 [Project Euler #15][C++] 20×20 격자의 좌상단에서 우하단으로 가는 경로의 수

   문제15 : 20×20 격자의 좌상단에서 우하단으로 가는 경로의 수 문제 아래와 같은 2 × 2 격자의 왼쪽 위 모서리에서 출발하여 오른쪽 아래 모서리까지 도달하는 길은 모두 6가지가 있습니다 (거슬러 가지는 않기로 합니다). 그러면 20 × 20 격자에는 모두 몇 개의 경로가 있습니까? 문제 해결 방법 격자에서 최단 경로의 수 를 찾는 문제이다.규칙성을 찾아 문제를 해결하였다.배열 ary[20][20]에서 ary[n][n] = ary[n - 1][n] + ary[n][n - 1]이다.for 문을 사용하여 ary[x][0]과 ary[0][x]의 값을 모두 1로 설정하였다.그리고 또 다른 for 문을 사용하여 찾은 규칙성을 바탕으로 배열에 값을 채워서 최종적으로 ary[SIZE][SIZE]에 있는 값이 출..
4. 2020.12.28 [Project Euler #14][C++] 백만 이하로 시작하는 우박수 중 가장 긴 과정을 거치는 것은?

   문제14 : 백만 이하로 시작하는 우박수 중 가장 긴 과정을 거치는 것은? 문제 양의 정수 n에 대하여, 다음과 같은 계산 과정을 반복하기로 합니다.n → n / 2 (n이 짝수일 때) n → 3n + 1 (n이 홀수일 때) 13에 대하여 위의 규칙을 적용해보면 아래처럼 10번의 과정을 통해 1이 됩니다. 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1 아직 증명은 되지 않았지만, 이런 과정을 거치면 어떤 수로 시작해도 마지막에는 1로 끝나리라 생각됩니다.(역주: 이것은 콜라츠 추측(Collatz Conjecture)이라고 하며, 이런 수들을 우박수(Hailstone Sequence)라 부르기도 합니다)그러면, 백만(1,000,000) 이하의 수로 시작했을 때 1까지 도달하는..
5. 2020.12.27 [Project Euler #13][C++] 50자리 수 100개를 더한 값의 첫 10자리 구하기

   문제13 : 50자리 수 100개를 더한 값의 첫 10자리 구하기 문제 아래에 50자리 수가 100개 있습니다. 이것을 모두 더한 값의 첫 10자리는 얼마입니까?37107287533902102798797998220837590246510135740250 46376937677490009712648124896970078050417018260538 74324986199524741059474233309513058123726617309629 91942213363574161572522430563301811072406154908250 23067588207539346171171980310421047513778063246676 89261670696623633820136378418383684178734361726757 28..
6. 2020.12.26 [Project Euler #12][C++] 500개 이상의 약수를 갖는 가장 작은 삼각수는?

   문제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개 이상의 약수를 갖는 가장 작은 삼각수는 얼마입니까? 문제 해..
7. 2020.12.26 [Project Euler #11][C++] 20×20 격자에서 연속된 네 수의 곱 중 최댓값

   문제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..
8. 2020.12.24 [Project Euler #10][C++]이백만 이하 소수의 합

   문제10 : 이백만 이하 소수의 합 문제 10 이하의 소수를 모두 더하면 2 + 3 + 5 + 7 = 17 이 됩니다. 이백만(2,000,000) 이하 소수의 합은 얼마입니까? 문제 해결 방법 하나하나씩 계산하는 방식(브루트 포스 방식)으로 문제를 해결하였다. (에라토스네스 체 알고리즘 사용)정답을 구하는데 약 20분 이 걸렸다. (...)for 문을 사용하여 문제를 해결하였다.2부터 N(2000000)까지 순회를 하며 소수를 찾으면 sum 변수에 대입하고 더하는 과정을 반복하였다.최종적으로 sum 변수에 할당된 값을 출력하도록 하였다. 소스 코드 1234567891011121314151617181920212223242526272829#include using namespace std; #define N..
9. 2020.12.23 [Project Euler #9][C++] a + b + c = 1000 이 되는 피타고라스 수

   문제9: a + b + c = 1000 이 되는 피타고라스 수 문제 세 자연수 a, b, c 가 피타고라스 정리 a² + b² = c² 를 만족하면 피타고라스 수라고 부릅니다 (여기서 a < b < c).예를 들면 3² + 4² = 9 + 16 = 25 = 5²이므로 3, 4, 5는 피타고라스 수입니다. a + b + c = 1000 인 피타고라스 수 a, b, c는 한 가지 뿐입니다. 이 때, a × b × c 는 얼마입니까? 문제 해결 방법 하나하나씩 계산하는 방식(브루트 포스 방식)으로 문제를 해결하였다.3중 for문을 사용하여1부터 N(1000)까지 순회를 하며 다음의 조건을 만족시켰을 때의 a, b, c 값의 곱을 ans 변수에 할당하였다.a < b < c(a * a) + (b * b) == (..
10. 2020.12.22 [Project Euler #8][C++] 1000자리 수 안에서 이어지는 5개 숫자의 곱 중 최댓값은?

    문제8: 1000자리 수 안에서 이어지는 5개 숫자의 곱 중 최댓값은? 문제 다음은 연속된 1000자리 수입니다 (읽기 좋게 50자리씩 잘라 놓음). 73167176531330624919225119674426574742355349194934969835203127745063262395783180169848018694788518438586156078911294949545950173795833195285320880551112540698747158523863050715693290963295227443043557668966489504452445231617318564030987111217223831136222989342338030813533627661428280644448664523874930358907296290..
11. 2020.12.22 [Project Euler #7][C++] 10001번째의 소수

    문제7: 10001번째의 소수 문제 소수를 크기 순으로 나열하면 2, 3, 5, 7, 11, 13, ... 과 같이 됩니다. 이 때 10,001번째의 소수를 구하세요. 문제 해결 방법 하나하나씩 계산하는 방식(브루트 포스 방식)으로 문제를 해결하였다.2중 for문을 사용하여1부터 N까지 순회를 하면서 소수의 조건(나머지가 1과 그 자신인 수) 을 만족시키는 수가 발견될 경우 count의 값을 1씩 증가시켰다.count의 값이 NUM(10001)이 되었을 때의 값을 ans 변수에 할당하고, 2중 for문에서 빠져나오도록 하였다.NUM(10001)번째 소수가 담긴 ans 변수의 값을 출력하도록 하였다.연산을 빠르게 하도록 하기 위해 register 변수를 사용하여 for문을 순회하도록 하였다. 소스 코드 1..
12. 2020.12.22 [Project Euler #6][C++] 1부터 100까지 "제곱의 합"과 "합의 제곱"의 차는?

    문제6: 1부터 100까지 "제곱의 합"과 "합의 제곱"의 차는? 문제 1부터 10까지 자연수를 각각 제곱해 더하면 다음과 같습니다 (제곱의 합). $1^{2} + 2^{2} + ... + 10^{2} = 385$ 1부터 10을 먼저 더한 다음에 그 결과를 제곱하면 다음과 같습니다 (합의 제곱). $(1 + 2 + ... + 10)^{2} = 55^{2} = 3025$ 따라서 1부터 10까지 자연수에 대해 "합의 제곱"과 "제곱의 합" 의 차이는 3025 - 385 = 2640 이 됩니다. 그러면 1부터 100까지 자연수에 대해 "합의 제곱"과 "제곱의 합"의 차이는 얼마입니까? 문제 해결 방법 하나하나씩 계산하는 방식(브루트 포스 방식)으로 문제를 해결하였다.for문을 사용하여자연수 1부터 N(100)..
13. 2020.11.16 [Project Euler #5][C++] 1 ~ 20 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수

    문제5 : 1 ~ 20 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수 문제 1 ~ 10 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 2520입니다. 그러면 1 ~ 20 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 얼마입니까? 문제 해결 방법 하나하나씩 계산하는 방식(브루트 포스 방식)으로 문제를 해결하였다.문제의 조건을 만족시키는 범위를 알 수 없는 수를 찾기 위해 unsigned long long int 자료형을 사용하였다.표현 가능 범위 : 0 ~ 18,446,744,073,709,551,6152중 for 문을 사용하였다.시간 복잡도 : O(n²)1부터 ULLONG_MAX까지 순회하는 for 문1부터 N(20)까지 순회하는 for 문1부터 ULLONG_MAX까지 순회하는 수 중에서,..
14. 2020.11.15 [Project Euler #4][C++] 세자리 수를 곱해 만들 수 있는 가장 큰 대칭수

    문제4 : 세자리 수를 곱해 만들 수 있는 가장 큰 대칭수 문제 앞에서부터 읽을 때나 뒤에서부터 읽을 때나 모양이 같은 수를 대칭수(palindrome)라고 부릅니다. 두 자리 수를 곱해 만들 수 있는 대칭수 중 가장 큰 수는 9009 (= 91 × 99) 입니다. 세 자리 수를 곱해 만들 수 있는 가장 큰 대칭수는 얼마입니까? 문제 해결 방법 팰린드롬 찾기 알고리즘 을 이용하여 문제를 해결하였다.우선, 팰린드롬 검사 함수(bool findPalindrome(string ary))를 만들었다.2중 for 문을 사용하여 100부터 999까지 순회를 하면서 곱한 수를 string형으로 바꾼 후(to_string(i * j)), 하나하나씩 팰린드롬 검사를 수행하였다. (findPalindrome(to_stri..
15. 2020.10.26 [Project Euler #3][C++] 가장 큰 소인수 구하기

    문제3: 가장 큰 소인수 구하기 문제 어떤 수를 소수의 곱으로만 나타내는 것을 소인수분해라 하고, 이 소수들을 그 수의 소인수라고 합니다.예를 들면 13195의 소인수는 5, 7, 13, 29 입니다. 600851475143의 소인수 중에서 가장 큰 수를 구하세요. 문제 해결 방법 소인수 분해 알고리즘 을 이용하여 문제를 해결하였다.어떤 수 num를 소인수 분해 하려면 num를 2부터 차례대로 num의 제곱근까지의 숫자로 나누어 떨어지는지 검사하면 된다.플로우 차트를 기반으로 문제를 해결하여도 되지만, 코드가 길어지기 때문에 while 문을 사용하여 문제를 해결하였다. 소스 코드 1234567891011121314151617181920#include using namespace std; long long..
16. 2020.10.24 [Project Euler #2][C++] 피보나치 수열에서 4백만 이하이면서 짝수인 항의 합

    문제2 : 피보나치 수열에서 4백만 이하이면서 짝수인 항의 합 문제 피보나치(Fibonacci) 수열의 각 항은 바로 앞의 항 두 개를 더한 것입니다. 1과 2로 시작하는 경우 이 수열은 아래와 같습니다. 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...4백만 이하의 짝수 값을 갖는 모든 피보나치 항을 더하면 얼마가 됩니까? 문제 해결 방법 문제의 조건을 잘 확인해야 한다.4백만 이하의 짝수 값 을 갖는 모든 피보나치 항을 더하라.즉, 피보나치 항의 값이 4백만 이하인 수 중에서 짝수 값을 갖는 모든 피보나치 항을 더하는 문제이다.나는 문제를 잘못 이해해서 연산을 4백만 번 수행 하는 작업을 반복하였고, 계속 오답 처리가 되어 멘탈이 붕괴되는 상황을 맞닥드리게 되었다.문제 번역자가 변..
17. 2020.10.24 [Project Euler #1][C++] 1000보다 작은 자연수 중에서 3 또는 5의 배수를 모두 더하면?

    문제1 : 1000보다 작은 자연수 중에서 3 또는 5의 배수를 모두 더하면? 문제 10보다 작은 자연수 중에서 3 또는 5의 배수는 3, 5, 6, 9 이고, 이것을 모두 더하면 23입니다. 1000보다 작은 자연수 중에서 3 또는 5의 배수를 모두 더하면 얼마일까요? 문제 해결 방법 for 문을 사용하여 1이상 1000 미만의 범위에서 해당 수가 3 또는 5로 나누어질 경우, 그 값들의 축적합을 구하도록 프로그램을 구현하였다. 소스 코드 123456789101112131415161718#include using namespace std; #define MAX_NUM 1000 int main() { int sum = 0; for (int i = 1; i