Project Euler 공략팁

프로젝트 오일러에 있는 많은 문제들은 컴퓨터 공학 / 전산학의 알고리즘 쪽에서 많이 다루는 문제들 — 최단 경로 문제라거나 특정한 형태의 dynamic programming ((동적계획법? 우리말로 뭐라고 부르는게 좋을까 -_-a )) — 부터 시작해서 약간 수학적인 문제에 이르기까지 다양한다.

프로젝트 오일러가 재밌고, 도전적인(…) 이유 중 하나는 인터넷을 뒤져봤자 답이 나올리가 없다는 것. 혹은 답이 나와있긴하지만 작은 크기에서나 유효한 설명이라 의미가 없다거나 하는건데… 그래도 못 풀면 여러가지로 스트레스니(…) 이걸 공략하기 위해서 내가 동원했던 것들을 간략히 정리. 사실 이런 공략법을 쓰는 이유는 수학에 약한게 제일 크다 Orz ((내가 컴퓨터 공학 전공이라 그런지, 일단 프로그래밍 쪽 팁은 없다(?) ))

문제의 의미를 찾기

평소에 별로 본 일이 없는 단어 — right angle triangle이 뭔지 프로젝트 오일러 하고나서야 처음 알았다 -_-;; — 들이라거나, 잘 이해가 안되는 수학적 개념들, 혹은 쉽게 계산할 방법이 없나 싶은 특정 함수들의 정의를 검색해보는 것.

여러 곳 뒤질 것도 없이 Mathematica를 만드는 Wolfram의 mathworld (http://mathworld.wolfram.com/) 라거나 위키백과를 검색한다. 그럼 하다못해 해당 성질이나 함수를 풀어 쓴 것을 읽어볼 수 있다.

예를 들어 굉장히 자주 만나게 되는 ((문제에서 직접 보여주거나, 밑에 깔려있거나)) 오일러 파이 함수 (Euler’s phi function; Euler’s totient function) 의 경우, 특정 숫자 n에 대해 n보다 작고, n과 서로소(coprime)인 숫자의 갯수인데 개념적으로는, 1 .. n – 1로 n을 나눠보면 된다(…).

하지만 실제로는 서로소인 p, q에 대해서

phi(p * q) = phi(p) * phi(q)

가 되서 이 성질을 사용해서 쉽게(?) 구할 수 있다.

Sloane’s 검색

이건 초기에 알았다면 참 유용했을 법하지만; 나중에도 약간은 도움이 된다.
OEIS — Open Encyclopedia of Integer Sequence — 혹은 Sloane’s list라고 부르는 정수 순열들의 사전/검색기인데, 큰 문제를 풀 때, 보통 작은 크기에서 시험적으로 풀어보게되는데, 그 값들이 자기가 생각한데로 구해진건지 확인하는데 매우 유용하다.

예를 들어서,

1,1,2,2,4,2,6,4,6,4

로 검색하면 위에서 언급한 오일러 파이 함수를 포함해서 10개 정도의 수열이 검색된다. 특정 함수에 대한 자신의 생각을 간단히 테스트할 수 있다는게 답이 맞다/틀리다만 판단해주는 프로젝트 오일러의 특성상 무지 도움이 된다(..).

라이브러리 써먹기

큰 수를 지원하는 언어들이 편하다. 하지만 왠간히 큰 수는 64bit 정수로도 충분하기 때문에 C/C++도 안될건 없긴하다(…). 하지만 유리수를 쉽게 다룰 수 있거나하면 편한 경우가 많다.

혹은 C++의 next_permutation 처럼 순열을 쉽게 나열(enumerate)할 수 있는 언어들도 편하게 쓸 수 있다(의외로 순열을 하나씩 보게되는 녀석들이 있다).

이산수학

이산수학 교재였던 Rosen의 Discrete Mathematics가 참 도움이 되었다. 가끔 다시 들춰볼때마다 느끼는건데, 이산수학 내용만 다 알아도 3학년과정까지의 컴퓨터 공학 전반을 이해할 수 있다(…). 특히나 Counting/Advanced counting에서 언급하는 enumeration 방법이나 초반에 나오는 recurrence relation 같은건 여러모로 쓸모가 있다…