오일러 프로젝트

Project Euler

영리여부	아님
사이트 종류	문제 풀기 웹사이트
회원 가입	자유로움
제작자	Colin Hughes (aka Euler)
시작일	2001년 10월 5일
웹사이트	projecteuler.net

오일러 프로젝트(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번의 연산을 하나의 완전한 합 공식으로 바꿀 수 있다.

$sum(n)=\sum _{i=1}^{\lfloor {\frac {n}{3}}\rfloor }3i+\sum _{i=1}^{\lfloor {\frac {n}{5}}\rfloor }5i-\sum _{i=1}^{\lfloor {\frac {n}{15}}\rfloor }15i$

$\sum _{i=1}^{n}ki=k{\frac {(n)(n+1)}{2}}$

파이썬 구현

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