Lamanus' Archive: Project Euler

레이블이 Project Euler인 게시물을 표시합니다. 모든 게시물 표시

2013. 12. 11.

Project Euler - 문제 12번

Highly divisible triangular number

Problem 12

The sequence of triangle numbers is generated by adding the natural numbers. So the 7^th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Let us list the factors of the first seven triangle numbers:

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

We can see that 28 is the first triangle number to have over five divisors.
What is the value of the first triangle number to have over five hundred divisors?

문제 12번 : Triangle number의 수열은 자연수를 더하여 생성된다. 그래서 7번째 Triangle number는 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28이 될 것이다. 그리고 처음 10개의 항은 다음과 같다:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

이제 처음 7항의 약수들을 나열해보자:

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

그러면 우리는 28이 처음으로 다섯 개의 약수를 가지는 Triangle number임을 알 수 있다. 그러면 처음으로 오백개의 약수를 가지는 Triangle number는 얼마인가?

이 문제의 핵심은 약수의 갯수를 구하는 방법인 것 같습니다. 일반적으로 약수의 갯수는 소인수를 통해서 바로 알 수 있습니다. 임의의 숫자 $L$이 소인수 $p_i$들로 이루어져 있다고 할 경우, 약수의 갯수 $n$은 다음과 같이 주어집니다.
$$
L=p_1^{n_1} \times p_2^{n_2} \times \cdots \quad \Rightarrow \quad n=(n_1 + 1) \times (n_2+1) \times \cdots
$$
그러면 소인수분해를 한 뒤에 약수의 갯수를 위와 같이 구하는 코드를 작성하면 됩니다.

int num_div(int n)
{
 int num_cal = 1;
 int temp = 0;
 
    while(n%2 == 0)
    {
        n = n/2;
        temp++;
 }
    num_cal *= temp+1;

    for(int k = 3; k < sqrt(n); k += 2)
    {
  temp = 0;
     while(n%k == 0)
     {
      n = n/k;
      temp++;
     }
     num_cal *= temp+1;
     
     if(n == 1)
      break;
    }
    if(n != 1)
     num_cal *= 2;
     
    return num_cal;
}

이처럼 소인수분해를 하여 바로 약수의 갯수를 리턴하는 함수를 이용하여 약수의 갯수가 500개를 최초로 넘어가는 숫자를 찾으면 결과는 아래와 같이 나타납니다.

2013. 11. 17.

Project Euler - 문제 11번

Largest product in a grid

Problem 11

In the 20

20 grid below, four numbers along a diagonal line have been marked in red.

02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08

49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00

49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65

70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91

31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80

47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50

98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70

26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21

55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72

36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95

17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92

39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57

56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58

80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40

52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66

36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69

42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36

69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16

73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54

70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48

The product of these numbers is 26

14 = 1788696.
What is the greatest product of four adjacent numbers in the same direction (up, down, left, right, or diagonally) in the 20

20 grid?

문제 11번 : 아래 주어진 20

20 격자에서 대각선으로 놓인 숫자 4개가 빨간색으로 표시되어 있다. 그 숫자들의 곱은 26

14 = 1788696 이다. 그러면 같은 방향(위, 아래, 왼쪽, 오른쪽, 또는 대각선)으로 붙어있는 숫자 4개의 가장 큰 곱은 얼마인가?

먼저 당면한 과제는 위에 주어진 숫자들을 어떻게 받아올 것인지 하는 부분입니다. 결국은 무식하게 숫자 사이사이에 , 를 넣고 2차원 배열을 이용해서 받았는데... 별로 권장하고 싶은 방법은 아니더군요. 계속 주어진 숫자를 이용하는 문제들이 나오는데 좋은 방법을 찾아봐야 할 것 같습니다.

아무튼 숫자들을 배열에 넣고 나면 사실, 코드 자체는 어려울 것이 없습니다. 같지만 다른 방향으로 4번만 반복하면 되기 때문이지요. 수평방향, 수직방향, 그리고 대각선 두 방향을 각각 생각해 주시면 됩니다. For문을 통해서 계산을 할 것이기 때문에 어떤 경우에 index가 1부터 20까지 가야 할 수도 있고 어떤 경우에는 1부터 17까지만 가야 할 수도 있습니다. 18을 넘어가면 숫자가 3개만 남는 경우가 생기기 때문이지요.

 int result = 0;
 // vertical
 for(int i = 0; i < 20; i++)
 {
  for(int j = 0; j < 17; j++)
  {
   int temp = num[j][i];
   for(int k = 1; k < 4; k++)
   {
    temp = temp*num[j+k][i];
    if(temp == 0)
    {
     j += k;
     break;
    }   
   }
   if(temp > result)
    result = temp;
  }
 }

제가 짠 수직방향 코드만 첨부합니다. 다른 방향은 index만 살짝 고쳐주면 되기 때문에 별로 어려운 부분은 아닌 것 같네요. 중간에 값이 0인 경우는 빠른 계산을 위해서 건너뛰게끔 했는데, 이 부분은 대각선 파트에선 지워버렸습니다. 대각선에서는 숫자를 대각선으로 카운팅해야 건너뛰는게 성립되는데 영 복잡해져서 약간의 시간을 감수하고 없애버렸네요.

결과는 바로 잘 나왔습니다. 시간도 거의 걸리지 않네요. 그래봐야 겨우 400개짜리 숫자들이었으니... 다만 격자가 커진다면 결과가 많이 달라지겠지요. 코드가 거진 $O(n^2)$ 정도이기 때문에 숫자가 크면 꽤나 불리한 코드입니다.

2013. 11. 14.

Project Euler - 문제 10번

Summation of primes

Problem 10

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
Find the sum of all the primes below two million.

문제 10번 : 10보다 작은 소수의 합은 17이다. 그러면 200만 이하의 모든 소수의 합은 얼마인가?

문제는 간단합니다. 그렇지만 소수 문제는 항상 시간을 얼마나 걸려서 답을 얻는지가 중요합니다. 이번 문제는 사실 앞서 문제 7번에서 썼던 코드를 살짝 고쳐서 사용하면 쉽게 답을 얻을 수 있습니다. 주의할 점은, 답이 int로 들어가지 않아섯 long long으로 정의하니 제대로 나오더군요.

#include <iostream>
#include "time.h"
#include "math.h"
using namespace std;

int main()
{
 clock_t start = clock();

 int j;
 long long result = 2;  // First prime number. 
 
 for(int i = 3; i < 2000000; i += 2)
 {
  for(j = 3; j*j < i; j += 2)
  {
   if(i%j == 0)
    break;
  }
  if(j > sqrt(i))
   result += i;
 }
    
 clock_t end = clock();
    cout << "Result : " << result << endl;
    cout << "Time : " << (long double)(end-start)/CLOCKS_PER_SEC;
    return 0;
}

이 코드로 답을 얻는데 무려 0.365초나 걸렸습니다.

제 코드는 아무리 줄여도 여기서 별반 차이가 나지 않을 것 같습니다. 그런데, 답을 입력하고 forum에서 보니까 소수의 합에 관한 아주 유용한 수학적인 툴이 있었습니다. 그 사람은 같은 구간동안 C++로 계산한 결과 700micro second가 걸렸다고 합니다. 즉, 0.0007초 인 셈인데, 제 코드보다 무려 500배나 빠른 셈이죠.

자세한 수학적인 내용을 찾아서 올리려고 했는데 잘 안나오네요. 찾게 되면 업데이트 하겠습니다.

Project Euler - 문제 9번

Special Pythagorean triplet

Problem 9

A Pythagorean triplet is a set of three natural numbers, a

b

c, for which,

a² + b² = c²

For example, 3² + 4² = 9 + 16 = 25 = 5².
There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.

문제 9번 : 피타고라스 triplet은 세 숫자의 집합으로, a

b

c 이며, 다음의 조건을 만족한다. 예를 들어서, 3² + 4² = 9 + 16 = 25 = 5². 피타고라스 triplet 중에서 a + b + c = 1000을 만족하는 triplet은 오직 한 쌍이 존재한다. 이 때 abc를 구하여라.

이 문제는 단순하게 계산하면 되기도 하지만, 빠른 속도로 결과를 구하기 위해서 위키피디아를 검색해 보았습니다. 그랬더니, Euclid's formula 라는 방법으로 세 숫자를 두 변수로 표현할 수 있고 또한 우리가 가진 조건을 통해서 보다 쉽게 답을 얻을 수 있습니다. 먼저, Euclid's formula를 살펴보면
$$a = m^{2}-n^{2}, \qquad b = 2mn, \qquad c = m^{2}+n^{2},$$이렇게 주어지고 여기서 조건은 $m>n$ 입니다. 이 공식과 주어진 조건을 합하면,
$$a+b+c=2m(m+n)=1000, \quad \Rightarrow \quad m(m+n)=500.$$그러면, 우리가 $m>n$ 이라고 했기 때문에 m이 가질 수 있는 최소 최대 값은 다음과 같이 얻을 수 있습니다.
$$ m^2 < m(m+n) = 500 < 2m^{2}.$$그러면 m의 값이 제약이 되므로 for문 하나는 위의 m에 대한 범위를 주고 다른 하나는 n을 1부터 m까지 주면 훨씬 짧은 시간 안에 피타고라스 triplet을 m과 n을 통해서 얻을 수 있습니다.

#include <iostream>
#include "time.h"
#include "math.h"
using namespace std;

#include <iostream>
#include "time.h"
#include "math.h"
using namespace std;

int main()
{
 clock_t start = clock();
 // Use Euclid's formula : a=m^2-n^2, b=2mn, c=m^2+n^2
 int result;
 for(int m = sqrt(500/2); m*m < 500; m++)
 {
  for(int n = 1; n < m; n++)
  {
   if(m*(m+n) == 500)
    result = (m*m-n*n)*(m*m+n*n)*2*m*n;
  }
 }
 
 clock_t end = clock();
    cout << "Result : " << result << endl;
    cout << "Time : " << (long double)(end-start)/CLOCKS_PER_SEC;
    return 0;
}

그러면 손쉽게 답을 얻을 수 있고 그 값은 아래와 같이 나옵니다.

Project Euler - 문제 8번

Largest product in a series

Problem 8

Find the greatest product of five consecutive digits in the 1000-digit number.

73167176531330624919225119674426574742355349194934

96983520312774506326239578318016984801869478851843

85861560789112949495459501737958331952853208805511

12540698747158523863050715693290963295227443043557

66896648950445244523161731856403098711121722383113

62229893423380308135336276614282806444486645238749

30358907296290491560440772390713810515859307960866

70172427121883998797908792274921901699720888093776

65727333001053367881220235421809751254540594752243

52584907711670556013604839586446706324415722155397

53697817977846174064955149290862569321978468622482

83972241375657056057490261407972968652414535100474

82166370484403199890008895243450658541227588666881

16427171479924442928230863465674813919123162824586

17866458359124566529476545682848912883142607690042

24219022671055626321111109370544217506941658960408

07198403850962455444362981230987879927244284909188

84580156166097919133875499200524063689912560717606

05886116467109405077541002256983155200055935729725

71636269561882670428252483600823257530420752963450

문제 8번 : 다음의 1000자리 숫자 속에서 가장 큰 다섯 숫자의 연속적인 곱을 찾으시오.

아... 처음에 이걸 보고 막막해지더군요. 이걸 어떻게 입력을 받아야하나... 싶었는데, 일단 string으로 받은 다음에 각각의 숫자를 string.at(i)로 꺼낸 다음, int 배열에 저장하는 방법으로 해결했습니다. 이렇게 되면, string에서 나온 숫자들은 배열에 들어갈 때에 숫자로 들어가지 못하고 ASCII 코드로 들어가게 되는데, 0부터 9까지의 숫자들이기 때문에 그냥 ASCII 코드에서 48만큼 빼주면 정확히 그 숫자와 같게 됩니다. 일종의 편법이지요.

그래서 이를 통해 길이 1000짜리 배열에 모조리 저장하고 연속적으로 5개씩 곱하면서 가장 큰 곱을 찾는 방법을 쓰는데, 계산 속도를 빠르게 하기 위해서 0을 만날 경우에는 5칸씩 건너뛰는 방법을 사용했습니다. 어차피 0이 한번 나오기 시작하면 5번동안 0이 걸리면서 모든 결과가 0이 되기 때문에 무의미하기 때문이지요.

#include <iostream>
#include "time.h"

using namespace std;

int main()
{
 clock_t start = clock();
 
 string numbers;
 numbers = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450";
 int num[numbers.length()];
 
 for(int i = 0; i < numbers.length(); i++)
  num[i] = numbers.at(i) - 48;  // ASCII code to int
 
 int result = 0;
 for(int i = 0; i < numbers.length()-5; i++)
 {
  int temp = num[i];
  for(int j = 1; j < 5; j++)
  {
   temp = temp * num[i+j];
   if(temp == 0)
   {
    i += j;
    break;
   }
   else if(temp > result)
    result = temp;
  }
 }
 
 clock_t end = clock();
    cout << "Result : " << result << endl;
    cout << "Time : " << (long double)(end-start)/CLOCKS_PER_SEC;
    return 0;
}

이렇게 해서 결과를 구하면 바로 답이 나옵니다.

결과는 정답! 중간에 실수했는데도 정답이 나와서 아무 생각없이 맞은 코드인줄 알았는데, 나중에 확인하고 고쳤네요.

Project Euler - 문제 7번

10001st prime

Problem 7

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.
What is the 10 001st prime number?

문제 7번 : 처음 6개의 소수를 나열하면: 2, 3, 5, 7, 11, 그리고 13, 여기서 6번째 소수는 13임을 알 수 있다. 그러면 10,001번째 소수는 얼마인가?

단순하게 소수를 찾는 문제입니다. 소수를 찾아내는 방법은 여러 가지가 있겠지만 가장 무난하면서도 쉬운 방법은 임의의 숫자를 그 전의 숫자들로 모조리 나누어 보는 방법이지요. 다만 이 방법은 시간이 오래 걸리는 것이 단점입니다. 빠른 속도를 원하시면 위키피디아 같은 곳에서 소수를 찾는 더 좋은 수학적인 방법을 검색해 볼 수도 있습니다.

저는 짝수는 제외하고 오직 홀수만 테스트 해 보았습니다. 그렇게 하면 전체적인 프로세스를 1/4까지 줄일 수 있습니다. 그리고 임의의 숫자 i를 j로 나누어 가면서 j를 1씩 증가시킬 것인데, 여기서 j를 꼭 i까지 증가시킬 필요는 없습니다. 왜냐하면 소인수의 특성상 1부터 $\sqrt{i}$까지만 i%j == 0인지 체크를 해주면 그 위의 부분은 저절로 체크가 되기 때문에, 중복해서 체크를 할 필요가 없습니다. 그래서 이런 방식으로 다시 프로세스를 간편화 시킬 수 있습니다.

#include <iostream>
#include "time.h"

using namespace std;

int main()
{
 clock_t start = clock();
 
 int i,j;
 int nprime = 1;  // I will skip 1st prime number 2. 
 
 for(i = 3; nprime < 10001; i += 2)
 {
  if(i%2 ==0)
   break;
  for(j = 3; j*j < i; j +=2)
  {
   if(i%j == 0)
    break;
  }
  if(j*j > i)
   nprime++;
 }
    
 clock_t end = clock();
    cout << "Result : " << i-2 << endl;
    cout << "Time : " << (long double)(end-start)/CLOCKS_PER_SEC;
    return 0;
}

여기서 sqrt 대신에 j를 제곱해서 체크를 했습니다. 만약에 j의 제곱이 i보다 작을 때 나누어 떨어지는 숫자가 하나도 없었다면 i라는 숫자는 소수라는 뜻이 됩니다. 그래서 for문이 끝나면서 j = j+2가 되고 if문에서 j의 제곱이 i보다 커지기 때문에 조건문으로 이 소수가 몇 번째 소수인지 체크를 하면서 10,001번째 소수를 찾는 것입니다.

결과 출력에 i-2라고 적었는데 이것은 for문을 탈출하면서 i가 2가 증가하기 때문에 원래 우리가 for문 안에서 찾은 소수 i를 출력하려면 다시 2만큼 빼 주어야 합니다. 이것 때문에 고생했네요;

처음에 무식하게 돌렸을 때는 1초도 넘게 걸렸는데, 조건을 잘 주고 나니까 9ms가 걸렸네요. 이것도 사실 긴 시간이긴 합니다만, 저는 일단 만족합니다.

2013. 11. 13.

Project Euler - 문제 6번

Sum square difference

Problem 6

The sum of the squares of the first ten natural numbers is,

1² + 2² + ... + 10² = 385

The square of the sum of the first ten natural numbers is,

(1 + 2 + ... + 10)² = 55² = 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025

385 = 2640.
Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

문제 6번 : 자연수 첫 10항의 제곱들의 합은,

1² + 2² + ... + 10² = 385

그리고 자연수 첫 10항의 합의 제곱은,

(1 + 2 + ... + 10)² = 55² = 3025

그래서 자연수 첫 10항의 합의 제곱에서 제곱의 합을 뺀 차이는 3025

385 = 2640. 그러면 자연수 첫 100항의 합의 제곱에서 제곱의 합을 뺀 차이는 얼마인가?

문제 자체가 그렇게 어렵지 않고, 코딩도 매우 간단합니다. 그냥 For문을 통해서 제곱항의 합과 그냥 합을 구한 다음에, 합의 제곱에서 제곱항의 합을 빼주면 되는 문제라서 딱히 코드를 쉽게 짜거나 할 필요도 없네요.

#include <iostream>
#include "time.h"

using namespace std;

int main()
{
 clock_t start = clock();
 
 int sum_of_squares = 0;
 int square_of_the_sum = 0;
 
 for(int i = 0; i < 101; i++)
 {
  sum_of_squares += i * i;
  square_of_the_sum += i;
 }
 
 int result = square_of_the_sum * square_of_the_sum - sum_of_squares;
 
 clock_t end = clock();
    cout << "Result : " << result << endl;
    cout << "Time : " << (long double)(end-start)/CLOCKS_PER_SEC;
    return 0;
}

그러면 답이 바로 나옵니다.

Project Euler - 문제 5번

Smallest multiple

Problem 5

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

문제 5번 : 2520은 1부터 10까지 나머지 없이 나누어지는 가장 작은 숫자이다. 그러면 1부터 20까지 나머지 없이 나누어지는 가장 작은 숫자는 얼마인가?

문제는 생각보다 간단합니다. 그런데, 단순하게 1부터 20까지 곱하면 그 숫자는 가장 작은 숫자가 아닙니다. 왜냐하면, 4로 나누어지는 수는 이미 2로 나누어지기 때문이지요. 그래서 중복되게 나누어지는 부분을 최소화해서 가장 작은 숫자를 찾는 것이 목적입니다.

제가 문제를 푼 방법은, 20 이하의 모든 소수를 찾고, 그 소수의 n제곱이 20 이하인 경우에 그 숫자를 곱해가면서 원하는 숫자를 찾았습니다. 말이 약간 복잡한데, 예를 들어서 2라는 소수가 있으면 $2^4=16$은 20보다 작기 때문에 20보다 작은 숫자 중에서 2의 배수로 가장 큰 16을 곱하고 그 이후에 2로 나누어 떨어지는 숫자들은 모두 곱하지 않는 것이지요. 이런식으로 각각의 소수들의 가장 큰 가능성들을 곱합으로써 중복되는 곱들을 모두 피할 수 있게 됩니다.

for(int i = 2; i < 20; i++)
{
 for(j = 2; j < i; j++)
 {
  if(i%j == 0)
   break;
 }
 if(i == j)
 {
  for(int k = j; k < 20; k = k*j)
   result = result * j;
 }
}

그래서 위와 같은 코드를 통해서 중복되지 않게 가장 최소의 숫자를 만들어 나갈 수 있고 그 결과는 아래와 같습니다.

생각보다 큰 수가 나오긴 했지만, 시간은 1ms 이하로 걸리면서 손쉽게 답을 얻었습니다.

Project Euler - 문제 4번

Largest palindrome product

Problem 4

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91

99.
Find the largest palindrome made from the product of two 3-digit numbers.

문제 4번 : Palindromic 숫자는 앞뒤로 읽어도 같은 숫자를 말한다. 두 자리 숫자의 곱셈으로 이루어진 가장 큰 palindromic 숫자는 9009 = 91

99 이다. 그러면 세 자리 숫자의 곱셈으로 이루어진 가장 큰 숫자는 얼만인가?

약간씩 문제가 어려워지기 시작했습니다. 앞뒤로 읽어도 같은 숫자이며, 세 자리 숫자의 곱셈으로 이루어진 가장 큰 숫자를 찾는 문제인데, 이를 위해서는 앞뒤로 읽어도 정말 같은 숫자인지 체크를 해 주어야 합니다. 그래서 저는 아래의 코드를 사용해서 숫자가 앞뒤로 읽어도 같은지 체크 한 뒤에 메인 코드를 진행하였습니다.

int checker(int n)
{
 int l = length(n);
 int num[l-1];
 int count = 0;
 
 for(int a = 0; a < l; a++)
 {
  num[a] = n%10;
  n = n/10;
 }
 for(int a = 0; a < l/2; a++)
 {
  if(num[a] == num[l-1-a])
   count++;
 }
 if(count == l/2)
  return 1;
 else
  return 0;
}

여기서 숫자 n의 길이 length(n)은 함수로 정의하는데, 길이를 측정하는 방법은 여러 가지가 있을 수 있습니다. 그 후에 세 자리 숫자들의 곱을 일일히 checker에 넣어서 확인하고 그 결과를 바탕으로 가장 큰 값을 찾아 나가면 될 것 같습니다.

int main()
{
 clock_t start = clock();
 
 int result = 0; 
    for(int i = 100; i < 1000; i++)
    {
     for(int j = 100; j < i+1; j++)
     {
      if(checker(i*j) == 1 && i*j > result)
       result = i*j;
     }
    }
    
    clock_t end = clock();
    cout << "결과 : " << result << endl;
    cout << "시간 : " << (long double)(end-start)/CLOCKS_PER_SEC;
    return 0;
}

그러면 결과가 아래와 같이 나옵니다. 당연히 앞뒤로 봐도 같은 숫자가 나오겠지요.

이번엔 바로 정답이 나왔습니다.

2013. 11. 12.

Project Euler - 문제 3번

Largest prime factor

Problem 3

The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?

문제 3번 : 13195의 소인수는 5, 7, 13 그리고 29이다. 그러면, 600851475143의 가장 큰 소인수는 얼마인가?

일단 문제는 간단합니다. 소인수분해를 해서 가장 큰 소인수를 찾는게 목표입니다. 그러면 먼저 소인수분해를 하면 될 것 같네요. 가장 일반적으로, 2를 제외한 모든 소수는 홀수이기 때문에, 먼저 주어진 숫자를 2로 나눠 홀수로 만듭니다. 그러나 이미 주어진 숫자는 홀수군요?

이제 i=3부터 2씩 증가시키면서 mod를 취해 나머지가 0이면 주어진 숫자를 i로 나눠가면서 계속 소인수분해를 진행합니다. 어느 순간, 2씩 증가시키던 숫자 i가 소인수분해를 해 나가는 숫자와 같아지게 되고 이게 마지막 소수가 됩니다. 진행 과정상 마지막에 나오는 소인수가 가장 큰 소인수가 될 수밖에 없습니다.

이 과정에서 단점은, 소수가 아닌 경우에도 mod를 취해서 나머지를 확인해 나간다는 점입니다. 약간의 시간이 더 걸리게 되는데 주어진 숫자가 그렇게 크진 않아서 시간은 매우 적게 걸렸습니다. 코드를 보면 이해가 쉬울 것 같네요.

#include <cstdlib>
#include <iostream>
#include "time.h"
using namespace std;

int main()
{
    clock_t start = clock();
  
    long long n = 600851475143;
    long long i; 
    
    while(n%2 == 0)
        n = n/2;
        
    for(i = 3; i != n; i += 2)
    {
     while(n%i == 0)
         n = n/i;
    }
    
    clock_t end = clock();
    cout << "결과 : " << i << endl;
    cout << "시간 : " << (long double)(end-start)/CLOCKS_PER_SEC;
    return 0;
}

그러면 결과가 아래와 같이 짠! 하고 나타납니다.

중간에 실수를 좀 했었는데, 다행히도 이번에는 정답을 얻었습니다.

Project Euler - 문제 2번

Even Fibonacci numbers

Problem 2

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

문제 2번 : 피보나치 수열에서 각각의 새로운 항은 그 전의 두 항을 더해서 만들어진다. 첫 두 항을 1과 2로 시작해서 첫 10개의 항은 다음과 같다:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

400만이 넘지 않는 피보나치 수열의 항들을 생각할 때에, 짝수 항들의 합은 얼마인가?

이미 손으로 풀 수 없는 숫자가 나왔습니다. 400만이 넘지 않는 피보나치 수열을 모조리 생각해야 하는데, 이걸 손으로 할 수는 없겠지요. 먼저 피보나치 수열의 정의를 알아야 합니다. 만약 피보나치 수열의 n번째 항을 $P(n)$이라고 하면,
$$P(n)=P(n-1)+P(n-2)$$
가 됩니다. 이후에 $P(n)$이 400만 이하가 되도록 while문을 주고, 짝수인지를 체크하면서 모두 더하면 될 것 같습니다.

#include <cstdlib>
#include <iostream>
#include "time.h"
using namespace std;

int main()
{
    clock_t start=clock();
  
    int p1=1;
    int p2=1; 
    int sum=0;
    
    while(p2<4000000)
    {
        if(p2%2==0)
           sum=sum+p2;
        int temp=p1; 
        p1=p2;
        p2+=temp;       
    }
    
    clock_t end=clock();
    printf("결과 : %d \n시간 : %lf", sum, end);
    return 0;
}

이렇게 코드를 짜면, p1은 p2를 내려받고 p2는 기존의 p1과 p2의 합으로 변하면서 p2항이 피보나치 수열을 계속 만들어가게 됩니다. 그 때에, p2가 400만 이하이면서 짝수이면 sum으로 모두 더해서 결과를 출력하도록 하였습니다.

결과값을 입력해주니 정답이 맞았네요! 앞선 포스트에서 말씀드린 것처럼, 결과는 가리도록 하겠습니다.

Project Euler - 문제 1번

Multiples of 3 and 5

Problem 1

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.

1번 문제 : 만약 우리가 3의 배수나 5의 배수 중에서 10보다 작은 숫자를 나열하면 3,5,6 그리고 9를 얻을 것입니다. 이 숫자들의 합은 23입니다. 그러면, 1000보다 작은 숫자들 중에서 3의 배수이거나 5의 배수인 숫자들의 합은 얼마일까요?

C++을 사용하면 mod를 이용해서 손쉽게 풀 수 있습니다. 제가 C++을 거의 모르는데, 문제들을 풀면서 하나씩 배워보려고 합니다. 먼저 저는 아래와 같이 코드를 작성해 보았습니다.

#include <cstdlib>
#include <iostream>

using namespace std;

int main(int argc, char *argv[])
{
    int n=1000;
    int sum=0;
    
    for(int i=1; i<n; i++)
    {
        if(i%3==0||i%5==0)
            sum=sum+i;
    }
    
    return sum;
}

컴파일을 하고 작동시켜보니 그 결과는 아래와 같이 나왔습니다.

그러면 이제 얻은 값을 Project Euler 홈페이지에 입력해 보겠습니다.

그러면...

정답입니다! 1번은 참 쉽군요. 앞으로는 코드만 일부 소개하고 정답은 가리도록 하겠습니다. Project Euler 정책에도 가급적이면 솔루션을 퍼트리지 말아달라고 하면서 정당한 경쟁을 할 수 있기를 바라더군요.

코딩 실력을 확인해보자! - Project Euler

Project Euler는 쉬운 문제부터 어려운 문제까지 다양한 난이도의 문제들을 주고 이를 자신만의 방법으로 해결하여 실력을 테스트 하는 곳입니다. 문제를 해결하기 위해서는 반드시 컴퓨터 프로그램을 필요로 합니다. 처음에는 손으로 풀 수도 있지만, 점점 문제의 난이도가 올라가고 엄청나케 큰 숫자까지의 결과를 요구하기도 하기 때문이지요.

문제를 풀고 나서 다른 사람들이 어떤 프로그램으로 코드를 어떻게 짰는지, 얼마나 시간이 걸렸는지 등을 확인할 수 있습니다. 홈페이지 제작자에 따르면, 알고리즘을 짜는 것이 어렵지, 실제로 결과를 얻는데 1분을 넘지 않도록 문제를 만든다고 합니다. 또한 사용자들에 관한 다양한 통계(사용하는 프로그램 언어, 사용자의 국가 등등)를 볼 수도 있습니다.

다만, 이곳에서 문제를 푸는데에는 약간의 수학적 지식을 필요로 합니다. 그냥 풀고자 하면 막막할 수도 있지만 수학적인 지식을 동원하면 좀 더 쉽게 알고리즘을 짤 수 있도록 되어 있습니다. 이곳에서 본인의 코딩 실력을 확인해 보는 것은 어떨까요? 앞으로 저도 이 문제들을 C언어로 풀어보면서 그 방법들을 포스팅해 보려고 합니다.

Project Euler 홈페이지 : http://projecteuler.net/