본문 바로가기
반응형

projecteuler19

[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.
[C++]프로젝트 오일러 17번 문제&풀이 (1부터 1000까지 영어로 썼을 때 사용된 글자의 개수는?) 문제 17번 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 글자가 됩니다. 접근방법 1. 숫자와 글자 갯수를 배열(array)에 담아 해당 수가 나오면 출력하는 구조로 진행. 2. 일단 배열에 글자 갯수를 넣어야.. 2020. 11. 26.
[C++]프로젝트 오일러 16번 문제&풀이 (2의 1000승의 각 자릿수를 모두 더하면?) 문제 16번 2^15 = 32768 의 각 자릿수를 더하면 3 + 2 + 7 + 6 + 8 = 26 입니다. 21000의 각 자릿수를 모두 더하면 얼마입니까? 접근방법 1. 2의 1000승을 계산 한 후 10씩 나누어 더하려고 하면, 담을 수 있는 연산자가 없기 때문에 풀 수 없다. 2. 1부터 시작해서 2씩 곱해 갈 때 바로바로 자릿수를 구하여, 각 자릿수를 벡터에 거꾸로 담는다. (벡터는 뒤에서부터 숫자가 담기기 때문 / 모든 값을 0으로 시작하고, 첫번째 위치에 1을 담고 시작한다.) 3. 각 자릿수를 2를 곱했을 때, 10을 넘지 않는 경우와 / 넘는 경우 2가지로 나눈다. (10을 넘는 경우, 그 칸에는 10으로 나눈 나머지를 넣고, 옆칸에 1을 더한다) 2^10까지만 해보면 2^0 : 1 / .. 2020. 11. 25.
[C++]프로젝트 오일러 15번 문제&풀이 (20×20 격자의 좌상단에서 우하단으로 가는 경로의 수) 문제 15번 아래와 같은 2 × 2 격자의 왼쪽 위 모서리에서 출발하여 오른쪽 아래 모서리까지 도달하는 길은 모두 6가지가 있습니다 (거슬러 가지는 않기로 합니다). 그러면 20 × 20 격자에는 모두 몇 개의 경로가 있습니까? 접근방법(1차) - 코드는 맨 밑에! 1. 중고등학생 때 시험문제로 종종 나왔던 문제라, 접근방법 찾는 것은 그리 어렵지 않다.(순열 문제임) (1X1) 격자의 경우 2, (2X2) 격자의 경우 6, (3X3) 격자의 경우 20, 이런 방식으로 구하면 된다. 2. 대각선으로 나열된 것을 가로로 배치해보면 3. 위와 같은 형태가 되고, 우리는 40C20 (콤비네이션 / 컴비네이션)을 구하면 된다. 4. 가장 먼저 생각해 볼 수 있는 것은 재귀함수이다. nCr = (n-1)C(r-1.. 2020. 11. 25.
[C++]프로젝트 오일러 14번 문제&풀이 (백만 이하로 시작하는 우박수 중 가장 긴 과정을 거치는 것은?) 문제 양의 정수 n에 대하여, 다음과 같은 계산 과정을 반복하기로 합니다. n → n / 2 (n이 짝수일 때) n → 3 n + 1 (n이 홀수일 때) 13에 대하여 위의 규칙을 적용해보면 아래처럼 10번의 과정을 통해 1이 됩니다. 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1 아직 증명은 되지 않았지만, 이런 과정을 거치면 어떤 수로 시작해도 마지막에는 1로 끝나리라 생각됩니다. (역주: 이것은 콜라츠 추측 Collatz Conjecture이라고 하며, 이런 수들을 우박수 hailstone sequence라 부르기도 합니다) 그러면, 백만(1,000,000) 이하의 수로 시작했을 때 1까지 도달하는데 가장 긴 과정을 거치는 수는 얼마입니까? 참고: 계산 과정에는 백만을.. 2020. 11. 24.
반응형

티스토리툴바