본문 바로가기
반응형

분류 전체보기146

[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.
[C++]프로젝트 오일러 13번 문제&풀이 (50자리 수 100개를 더한 값의 첫 10자리 구하기) 문제 아래에 50자리 수가 100개 있습니다. 이것을 모두 더한 값의 첫 10자리는 얼마입니까? 37107287533902102798797998220837590246510135740250 46376937677490009712648124896970078050417018260538 74324986199524741059474233309513058123726617309629 91942213363574161572522430563301811072406154908250 23067588207539346171171980310421047513778063246676 89261670696623633820136378418383684178734361726757 28112879812849979408065481931592621691.. 2020. 11. 24.
[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.
반응형

티스토리툴바