오일러 프로젝트 문서 원본 보기

{{위키데이터 속성 추적}}
{{웹사이트 정보
| 이름 = Project Euler
| 로고 = 
| 그림 =Leonhard Euler.jpg
| 설명 =
| 표어 = 
| 목적 = 
| 주소 = [http://projecteuler.net/ projecteuler.net]
| 영리적 = 아님
| 종류 = 문제 풀기 웹사이트
| 시작일 = [[2001년]] [[10월 5일]]
| 등록 = 자유로움
| 언어 =
| 수입 =
| 소유자 = 
| 제작자 = Colin Hughes (aka Euler)
| 상태 =
}}
'''오일러 프로젝트'''(Project Euler)는 컴퓨터 프로그램으로 수학 문제를 풀기 위해 만들어진 웹사이트이다. 이 프로젝트는 [[수학]]과 [[컴퓨터 프로그래밍]]에 흥미를 돋우기 위해 만들어졌다. [[2009년]] 5월, 이 프로젝트는 250개 이상의 다양한 난이도의 문제를 포함하고 있다. 각 문제는 효율적인 알고리즘이라면 현대의 컴퓨터로 1분 내에 풀 수 있다. 새 문제를 [[2001년]]부터 주기적으로 추가하고 있다. 문제에 바른 답을 제출한 사용자는 각 문제에 딸린 포럼을 볼 수 있다.<ref>{{웹 인용|url=http://projecteuler.net/index.php?section=about |제목=Project Euler - About |확인날짜=2008-04-04}}</ref>로그인 한 사용자는 문제를 푼 수에 따른 고득점자 순위를 볼 수 있다. 25문제를 풀 때마다 레벨이 올라가며, 독특한 앰블럼이 주어진다. 특정 조합의 문제들을 풀면 '상'을 얻을 수도 있다.

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

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

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

[[파이썬]]:
<syntaxhighlight lang="python">
print sum(x for x in range(1, 1000) if x%3==0 or x%5==0)
</syntaxhighlight>

[[C++]]:
<syntaxhighlight lang="cpp">
#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;
}
</syntaxhighlight>

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

: <math>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</math>

: <math>\sum_{i=1}^n ki = k\frac{(n)(n+1)}{2}</math>

파이썬 구현
<syntaxhighlight lang="python">
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)
</syntaxhighlight>

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

== 같이 보기 ==
* [[오일러의 법칙]]
== 각주 ==
<references />

== 외부 링크 ==
*{{언어링크|en}} [http://projecteuler.net/ 오일러 프로젝트]
*{{언어링크|ko}} [http://euler.synap.co.kr/ 오일러 프로젝트]
* [https://web.archive.org/web/20100522061217/http://eulerdz.toile-libre.org/ EulerDZ : Project Euler In French]

[[분류:교육 웹사이트]]
[[분류:문제 해결]]
[[분류:수학 교육]]
[[분류:수학 웹사이트]]
[[분류:퍼즐]]