프로젝트 오일러

프로젝트 오일러

개요

본격 수학 + 프로그래밍 챌린지

프로젝트 오일러(Project Euler)란, 익숙하지 분야에 대해 깊게 탐구할 수 있는 바탕과, 새로운 개념에 대해 재미있게 배울 수 있는 기회를 제공하기 위해 시작된 영국의 프로젝트다. 간단히 말하면, 그냥 프로그래밍으로 수학 문제 푸는 웹 사이트. 수학에 관심이 있다면 국가에 상관없이 누구나 이 프로젝트에 참여해 문제를 풀 수 있지만, 영어가 어느 정도 뒷받쳐줘야 한다. 한국어로 번역된 사이트도 존재하긴 하지만 번역 속도가 그리 빠른 편은 아니다. 영어 웹 사이트에는 500개가 넘는 문제가 등록되어 있는 반면, 한국 웹 사이트에는 100개 조금 넘는 문제만 번역이 되었기 때문에 더 많은 문제를 풀고 싶다면 영어가 필수. 사실 대부분의 사람들은 100 문제는 커녕 10 문제도 풀기 힘들다.

참여 방법

문제를 보는 것은 가입이 필요 없지만, 답안을 제출하고 맞았는지 틀렸는지 확인하기 위해서는 가입이 필수다. 가입이라고 해봤자 아이디랑 비밀번호 적는게 전부. 이메일 인증같은 것도 없다.

문제

웹 사이트에 있는 모든 문제는 수학적 지식을 필요로 하지만, 수학보다 더 중요한 것은 바로 프로그래밍 실력. 처음 몇 문제는 수학 실력이 되면 손으로 써서 풀 수 있지만, 조금만 넘어가면 프로그래밍이 필수. 설마 10001 번째 소수를 정말로 손으로 찾으려는 생각은 아니겠지? (7번 문제)

그나마 다행인 것은, 대부분의 문제가 심오한 수학적 이론을 필요로 하지 않고, 초·중·고등학교에서 배우는 것들을 활용하여 해결할 수 있다는 점. 예시로, 1번 문제를 풀어보자.

“

10 미만의 자연수 중 3과 5의 배수를 나열하면 3, 5, 6, 9가 있습니다. 이 배수의 합은 23입니다. 1000 미만의 자연수 중 3과 5의 배수를 모두 더한 값은 얼마인가요?

“

초등학교 때 풀어봤을 법한 문제다. 숫자가 1000 미만이기 때문에 마음만 먹으면 노가다로도 풀 수 있지만, 포함과 배제의 원리를 사용하면 간단하다.

[math]\displaystyle{ \sum_{x=1}^{\lfloor\frac{1000}{3}\rfloor}\left(3x\right)+\sum_{x=1}^{\lfloor\frac{1000}{5}\rfloor}\left(5x\right)-\sum_{x=1}^{\lfloor\frac{1000}{15}\rfloor}\left(15x\right)-1000 }[/math]

위 식을 풀면 답이다. 이 문제는 손으로도 쉽게 계산할 수 있지만, 프로그래밍을 쓴다면 포함과 배제의 원리를 쓸 필요도 없이 쉽게 문제를 풀 수 있다. 아래는 1번 문제를 푸는 자바 코드.

public class Problem1
{
    public static void main(String args[])
    {
        int sum=0;
        for(int x=1;x<1000;x++)
        {
            if (x%3==0 || x%5==0)
                sum += x;
        }
        System.out.println(sum);
    }
}

C# 코드

    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine(Enumerable.Range(1, 999).Where(i => i % 3 == 0 || i % 5 == 0).Sum());
        }
    }

물론, 당신이 이런 단순 무식한 프로그래밍 방법보다 효율적인 프로그램을 짜고 싶다면 말리진 않겠다. 다만, 효율적인 프로그램을 짜기 위해서는 그에 맞는 수학적 이론이 필요로 하단 사실만 알아두자.

만약 문제를 풀어 맞췄다면 해당 문제의 스레드를 볼 수 있다. 수많은 프로그래밍 실력자들의 효율적인 코드들을 볼 수 있으므로 프로그래밍을 공부한다면 참고하자.

관련 링크

• 원래 웹 사이트
• 한국 번역 사이트