요즘에 주말마다 혹은 시간 날 때마다 Project Euler 에 방문을 합니다.

이 웹페이지에는 200개 넘는 수학 문제가 있습니다. 가입하고 나면 답을 적어 넣을 수 있고, 답을 맞추다면 그 문제에 대한 토론 게시판에 접근할 수 있게 됩니다. 이 토론 게시판에는 어떻게 정답을 풀었는가에 대한 다양한 의견을 볼 수 있게 됩니다.

그럼 문제의 난이도는 어떨지 궁금하지요. 쉬운 문제부터 어려운 문제까지 다양합니다. 다만, 그냥 손으로 풀기는 좀 어렵습니다. 계산기를 써야 할까요? 아닙니다. 반드시 컴퓨터를 사용해야 할 겁니다. 문제는 쉬운데, 손으로 풀기는 어려울만큼 계산량이 필요로 합니다.

예를 들어, 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.

번역을 해 보면 [1000 이하의 수 중에서 모든 3과 5의 배수들의 합을 구하라]는 문제입니다.

물론 손으로 해결할 수 있지만, 프로그램 언어를 이용하거나 수학 도구를 이용한 다면 한 줄에 해결 되겠지요. 저 같이 Maple 을 사용하는 사람이라면 다음과 같이 한 줄로 해결할 수 있습니다.

 > add(i, i in select(x->modp(x,3)=0 or modp(x,5)=0, [$1..1000]));

물론 1000 이하의 3의 배수의 합을 계산하고, 5의 배수의 합을 계산하고, 15의 배수의 합을 계산하여 더하고 빼면 되겠지만.. 이제 다음 문제 부터는 그런 손으로 하는 노가다는 더 이상 힘들겁니다. 그리고 점점 계산량이 많아지기 때문에 효율적인 알고리즘을 만들지 않으면, 문제 해결 시간이 천문학적으로 늘어나더군요.

여기 문제를 풀면서 다른 사람의 풀이를 보니, 조금씩 계산을 위한 프로그램밍이 느는 것 같습니다. 여러분들도 한 번 도전해 보세요.

@ 참고로 제 아이디는 ensual 입니다. 지금 현재 저의 스코어는 66/273 입니다. 한국 참여자 중에서는 61/382 입니다. Maple 사용자 중에서는 24/149 입니다.

'Thoughts > Math' 카테고리의 다른 글

무한 급수  (4) 2010.08.04
피라미드 저울의 눈금 문제  (10) 2010.04.09
Project Euler  (6) 2010.01.15
IBM Research - Ponder This, 2010년 1월  (2) 2010.01.14
두 개의 행렬  (2) 2009.11.04
재밌는 시외버스 가격  (3) 2009.08.26
  1. 추유호 2010.01.17 16:48

    재미붙으셨군요. ㅎㅎㅎ :)
    저도 maple을 썼습니다만, 어설프게 배워서인지 썩 효율적인 프로그램은 잘 안 나오더군요. 요즘은 그나마도 안 풀고 있습니다만...-_-

    • Favicon of https://blog.hshin.info Ens 2010.01.17 17:54 신고

      C/C++, Java 같은 컴퓨터 프로그램 언어보다는
      Maple. Matlab 같은 수학 계산 전용 도구가 편한 것 같습니다.

      특히 maple 은 인수분해하는 ifactors. 소수 판별을 하는 isprime, 조합수학과 정수론을 위한 combinat, numtheory 패키지 등등..
      이미 짜여진 함수가 많고 따로 컴파일 할 필요가 없어서..
      머리 속에서 알고리즘이 떠올리는 데로 프로그래밍 할 수가 있거든요..

      암튼 덕분에 즐거운 싸이트를 알게 되어서 기쁩니다.

  2. 병철 2010.01.21 17:35

    C는 기본적으로 소수판변, 인수분해, Combination, Permutation 같은 것들부터 구현해야 한다는건 그렇다 치는데...

    가장 골치아픈건 정수론 문제인데, C의 정수 범위를 넘어가는 수가 나올때로군... -_-;;;
    (Maple 같은 녀석들은 애초부터 정수/실수를 구분 안하는 시스템일텐데)

    unsigned long 으로 잡을 수 있는 수 범위를 넘어갈때는 난감

    • Favicon of https://blog.hshin.info Ens 2010.01.21 21:21 신고

      그것을 넘어가는 숫자가 거의 안 나올텐데.. ^^;
      아마 로그를 취하거나 해서..
      아니면 전면적으로 다른 알고리즘으로 해결해야 하지 않을까?

      포럼에 가보면 C/C++ 사용자가 가장 많고, 잘 풀기도 하고..

  3. Favicon of http://snowall.tistory.com snowall 2010.04.26 09:20

    가끔 손으로 쉽게 풀 수 있는 문제도 나옵니다. -_-;

    • Favicon of https://blog.hshin.info Ens 2010.04.26 20:39 신고

      저는 손으로 풀 수 있는 쉬운 문제도.. 코드로 짜서 풉니다만..
      이것이 게을러진 건지.. 부지런해진 건지.. 잘 모르겠더군요..

+ Recent posts