Programming/Project Euler118 [C/C++] 프로젝트 오일러 #15 격자 경로의 수 구하기(조합) 사실 이번 문제는 상당히 쉬운 편이라서 그다지 설명이 필요할 것도 없을 듯 합니다. 다른 프로그래머도 저랑 비슷한 접근을 했고요. 2014년 년 마지막 날을 이렇게 보내네요. 이 문제는 격자(grid)를 기반으로 한 경로 계산 문제입니다. 다음은 문제의 배경과 요구사항입니다:문제 설명:2차원 격자가 주어졌을 때, 왼쪽 위 모서리에서 오른쪽 아래 모서리까지 이동하는 경로의 수를 계산합니다. 이때 이동은 오직 오른쪽 또는 아래쪽 방향으로만 가능합니다. 격자의 크기는 \(n \times n\) 으로 주어지며, 경로의 조합 수를 계산하는 것이 목표입니다.문제의 요구사항:• \(n \times n\) 크기의 격자에서 가능한 모든 경로의 수를 구하시오.• 경로의 수는 조합 수식을 사용하여 계산됩니다. 수학적.. 2014. 12. 31. [C/C++] 프로젝트 오일러 #14 Longest Collatz Sequence(동적 프로그래밍) 1백만보다 작은 수 중에서, 다음과 같은 콜라츠 수열을 생성할 때 가장 긴 수열을 만들어내는 초기값을 찾는 문제입니다.콜라츠 수열은 다음과 같은 규칙으로 정의됩니다:1. 어떤 정수 n 에 대해:• n 이 짝수이면, n 을 2로 나눕니다. ( n = n / 2 )• n 이 홀수이면, n 에 3을 곱하고 1을 더합니다. ( n = 3n + 1 )2. 수열은 n = 1 이 될 때 종료됩니다.예를 들어, 초기값이 13인 경우 수열은 다음과 같이 생성됩니다:\[ 13 \rightarrow 40 \rightarrow 20 \rightarrow 10 \rightarrow 5 \rightarrow 16 \rightarrow 8 \rightarrow 4 \rightarrow 2 \rightarrow 1 \]이.. 2014. 12. 30. [C/C++] 프로젝트 오일러 #13 BigInt 수의 합 구하기 프로젝트 오일러( Project Euler )의 13번 문제 Large Sum 은 다음과 같은 내용을 다룹니다:• 문제에서는 50자리로 이루어진 큰 수(Big integer) 100개가 주어집니다.• 이 100개의 수를 모두 더하여 얻은 합(누적값)을 구합니다.• 그렇게 구한 합의 가장 앞에서부터 10자리만을 추출하여 결과로 제시해야 합니다.즉, 핵심 요구사항은 “아래에 주어진 100개의 50자리 수를 모두 합한 뒤, 그 합의 처음 10자리를 구해라” 입니다. 사실 이번 문제는 꼼수로 푸는 것이 맞을 듯 합니다.BigInt 라이브러리를 이용해서 풀어도 되겠지만, 그렇게 하면 시간이 많이 걸리죠. 앞자리부터 10자리 숫자만 구하면 되는 것이니까요. 그렇게 하면 int형으로는 위험할지 몰라도 int64형으.. 2014. 12. 30. [C/C++] 프로젝트 오일러 #12 Highly Divisible Triangular Number 삼각수(triangular number)는 다음과 같이 자연수를 차례대로 더한 값으로 정의됩니다.\[ T_n = 1 + 2 + 3 + \dots + n = \frac{n(n+1)}{2} \]예를 들어, 처음 7개의 삼각수는 다음과 같습니다:1, 3, 6, 10, 15, 21, 28이 문제에서는, 500개 이상의 약수를 가지는 첫 번째 삼각수를 찾는 것이 목표입니다. 제가 작성한 소스입니다.//------------------------------------------------// Project Euler #12 - Highly Divisible Triangular Number// - by Aubrey Choi// - created at 2014-12-29//-------.. 2014. 12. 29. #11 : 그리드에서 가장 큰 곱수 구하기(Brute Force) 이번 문제는 사실 효율적인 알고리즘을 찾기가 어렵네요. 난이도 5%로 아주 쉬운 문제로 평가되어 있는 문제입니다. 탐욕 알고리즘을 이용해서 풀어볼려고 시도를 했는데, 탐욕 알고리즘이 늘 최선의 결과를 내는 것이 아니고, 오히려 정렬하는 시간 때문에 속도 향상을 기대하기 힘드네요. 400개의 데이터를 정렬하는 것 자체가, 순차적으로 모든 곱을 계산하는 것보다 기본적으로 점근적 접근상 더 큰 값을 가지니까요. 효율로 따져서 득 될 것이 없다고 생각했습니다. 제가 처음에 생각했던 탐욕 알고리즘은,가장 큰 수부터 차례대로 근처에 있는 곱을 계산하고, 현재의 최대값이 다음 가장 큰수의 네제곱수보다 크다면, 거기서 종료하는 방법이었습니다. 이 알고리즘으로 한다면, 제일 큰 곱수를 구할 수 있습니다만, 과연 이게.. 2014. 12. 28. 10. 프로젝트 오일러 #10 : 2백만 이하의 소수의 합 구하기 사실 이번 문제는 에라스토테네스의 체를 이용하는 것 이외에는 별다른 좋은 방법은 없어보입니다. 큰 수에 대해서는 효율적인 알고리즘을 개발할 수 있지만, 2백만이라는 비교적 작은 수에 대한 것이라서 간단하게 짜보았습니다. #define LIMIT 2000000 void solve1() { int primes[200000]; int count = 0; int64_t sum = 0; primes[count++] = 2; sum += 2; primes[count++] = 3; sum += 3; for( int p = 5 ; p < LIMIT ; p+=2 ) { bool isPrime = true; for( int i = 1; primes[i]*primes[i] 2014. 12. 24. 이전 1 ··· 15 16 17 18 19 20 다음
