오일러 프로젝트

오일러 프로젝트(Project Euler)는 컴퓨터 프로그램으로 수학 문제를 풀기 위해 만들어진 웹사이트이다. 이 프로젝트는 수학과 컴퓨터 프로그래밍에 흥미를 돋우기 위해 만들어졌다. 2009년 5월, 이 프로젝트는 250개 이상의 다양한 난이도의 문제를 포함하고 있다. 각 문제는 효율적인 알고리즘이라면 현대의 컴퓨터로 1분 내에 풀 수 있다. 새 문제를 2001년부터 주기적으로 추가하고 있다. 문제에 바른 답을 제출한 사용자는 각 문제에 딸린 포럼을 볼 수 있다.로그인 한 사용자는 문제를 푼 수에 따른 고득점자 순위를 볼 수 있다. 25문제를 풀 때마다 레벨이 올라가며, 독특한 앰블럼이 주어진다. 특정 조합의 문제들을 풀면 '상'을 얻을 수도 있다.

예제 문제와 풀이 
첫 번째 오일러 프로젝트 문제는 다음과 같다.
10 미만의 자연수 중 3과 5의 배수를 나열하면 3, 5, 6, 9가 있습니다. 이 배수의 합은 23입니다.

1000 미만의 자연수 중 3과 5의 배수를 모두 더한 값은 얼마인가요?

이 문제는 일반적인 문제에 비해 훨씬 쉽기 때문에 효율적인 알고리듬을 만드는 잠재적인 차이를 설명하는 데 쓰인다. 조잡한 알고리듬으로는 1000보다 작은 모든 자연수를 검사해 기준을 만족하는 수를 계속 더해 나가면 된다. 이 방법은 다음 서로 다른 언어를 통해 보는 예제와 같이 구현하기 쉽다.

파이썬:
print sum(x for x in range(1, 1000) if x%3==0 or x%5==0)

C++:
#include <iostream>
using namespace std;
int main( ) {
  int sum = 0;
  for (int i = 0; i < 1000; i++)
    if ( i % 3 == 0 || i % 5 == 0 )
      sum += i;
  cout << sum << endl;
  return 0;
}

더 어려운 문제일수록 효율적인 알고리듬은 중요해진다. 이 문제에 대해 포함배제의 원리를 이용하면 1000번의 연산을 하나의 완전한 합 공식으로 바꿀 수 있다.

 

 

파이썬 구현
def sum1toN(n):
   return n * (n + 1) / 2

def sumMultiples(limit, a):
   return sum1toN((limit - 1) / a) * a

sumMultiples(1000, 3) + sumMultiples(1000, 5) - sumMultiples(1000, 15)

산술 연산당 고정된 시간이 걸린다고 가정하면 대문자 O 표기법에 따르면 조잡하게 풀면 O(n) 이고 효율적인 알고리듬은 O(1)이다.

각주

외부 링크 
 오일러 프로젝트
 오일러 프로젝트
EulerDZ : Project Euler In French

교육 웹사이트
문제 해결
수학 교육
수학 웹사이트
퍼즐