[기획 연재] 수학과 프로그래밍 – Intro (프로젝트오일러 x 줄리아)

2016-07-12 | 개발 이야기

안녕하세요? 사이냅소프트입니다.

이전에 저희 블로그에서 <프로그래머의 길>이라는 주제로 기획 연재 했었던 거, 기억하시죠?

그 중에서도 <프로그래머의 수학 공부>라는 글은 그야말로 핫 이슈였답니다.

페이스북 “좋아요”를 눌러 주신 분이 1천 명을 훌쩍 넘겼으니까요!

개발자들이 수학에 대해 얼마나 많은 관심을 가지고 있는지 새삼 확인할 수 있었습니다.

그래서 이번에는 수학과 프로그래밍의 적절한 만남이 이루어지는 곳, 프로젝트 오일러(Project Euler)를 소재로 글을 올려보고자 합니다.
(Euler는 독일어라서 ‘오일러’ 라고 읽는답니다)

프로젝트 오일러는 https://projecteuler.net/ 라는 주소를 가진 웹사이트입니다. 수학 문제를 프로그래밍으로 풀어 보고, 그 문제를 맞힌 사람들은 다른 이들이 어떻게 풀었는지 포럼에서 구경도 할 수 있는 그런 사이트죠.

일단 한 문제라도 풀어보면 다른 문제도 풀어보고 싶게 만드는 묘한 매력이 있답니다. 어떤 문제는 계산기나 암산으로도 되지만 어떤 문제는 컴퓨터의 도움 없이는 답이 안 나오는 경우도 많고요…

레온하르트 오일러 (1707-1783)

하지만 내용이 영문으로 되어 있어서, 수학에 관심이 있어도 영어가 약한 사람들에게는 가까이 하기에 너무 먼 곳이었습니다. 사실 수학이라면 한국어도 쉽지 않은데 하물며 영어라니요….

A palindromic number reads the same both ways.

The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

Find the largest palindrome made from the product of two 3-digit numbers.

( Project Euler 4번 문제의 원문입니다. 와우! )

그런 이유로, 2012년 1월, 저희가 자발적으로 콘텐츠를 번역하고 자체 사이트를 통해 한국어 버전을 서비스하기 시작했답니다. 저번 <프로그래머의 수학 공부> 글에서도 잠깐 언급이 되었었는데요, http://euler.synap.co.kr/ 라는 주소로 방문할 수 있습니다. 사이트가 만들어지기까지는 사이냅 사장님의 수학 사랑이 한 몫 했다는 뒷얘기가… 🙂

원본 사이트로부터 콘텐츠 DB를 제휴받거나 한 것은 아니어서, 번역도 하고 문제도 풀고 (…) 하느라 업데이트가 자주 이루어지지 못하는 점은 아쉽네요. 그래도 많은 분들이 찾아주시는 것을 보며 앞으로도 꾸준히 유지하고 발전시켜 나가려고 합니다.

아래는 문제보기 화면이에요. 1번 문제는 아주 쉬운지 4천명이 넘게 풀어주셨네요!

서론이 좀 길었죠. 이제 본격적으로 진도를 나가기 전에 우리 문제 풀이를 도와줄 선수 소개를 하겠습니다. 프로젝트 오일러와 찹쌀떡 궁합, Julia 입니다.

Julia 공식 홈페이지 : http://julialang.org/

(영화배우나 철권 캐릭터, 프랙탈 등과는 별로 관련 없습니다)

생소한 분들도 계실텐데요, Julia는 프로그래밍 언어의 이름입니다. 그리 많이 알려지지는 않았지만 과학기술 분야(scientific computing)에서는 나름 인지도가 있는 편입니다. 비교 대상을 흔히 R이나 Python, Matlab 같은 언어로 잡으니까요.

Julia는 Python이나 Ruby 같은 스크립트 언어의 모양을 하고 있어요. 하지만 LLVM 기반의 JIT 컴파일러를 통해서, VM용 코드가 아닌 native code를 만들어내는 재주가 있답니다. 스크립트 언어인데 C언어에 가까운 성능을 기대할 수 있다는 이야기죠. 이 점이 Julia의 최대 매력 포인트!

하지만 우리는 프로젝트 오일러로 다시 관심을 모으려고 합니다. Julia는 문법이 괴이하거나 배우기 어려운 언어가 아니라서, 문제를 풀어가는 중에 자연스럽게 필요한만큼 알아보는 것으로 충분할 것 같네요.

앞으로는 다음의 순서로 프로젝트 오일러와 친해지는 시간을 마련해 보려 해요.

(1) 프로젝트오일러 x 줄리아

(2) 피보나치 _ #02, #25

(3) 약수 _ #12, #21

(4) 직각삼각형 _ #09, #39

(5) 맺으며

맛보기로 문제 하나 풀어보면서 이번 포스팅을 마칠께요.

프로젝트 오일러 — 3번, 소인수 관련 문제입니다.

Q. 600851475143의 소인수 중에서 가장 큰 수는?

A.

factor(600851475143) |> keys |> maximum

간단 설명.

factor : 소인수와 지수를 Dict (key-value) 형태로 구함
keys : Dict에서 key 부분만 추출
maximum : 컬렉션에서 최대값 구함
|> 연산자 : function chaining

간단 설명만으로도 어떻게 돌아가는지 아시겠다는 분은 센스 굿 ! (^^)b

하지만 혹시 모르니 좀 더 자세하게 설명해보겠습니다.

소인수 분해.. 사실 그냥 하려면 막막하거나 귀찮거나죠. 하지만 Julia에서는 기본 제공!
Julia 내장함수 factor는 어떤 수를 소인수분해해서 { 소인수 => 지수 } 처럼 Dict 형태로 돌려줍니다.
이거 참 편리하더라고요. 소인수 나오는 문제마다 유용하게 써먹을 수 있죠.

Dict는 짐작하시듯이 map 등으로도 불리는 associative array에요. { key => value } 의 모양이고요.
그러니까 예를 들어 factor(40) 의 경우에는, 40 = 2 x 2 x 2 x 5 = 2의 3승 x 5의 1승… 이니까
{ 2 => 3, 5 => 1 } 의 결과를 돌려줍니다.

이번 문제를 푸는데 필요한건 2, 5 같은 소인수 부분이므로, 결과 Dict에서 key만 뽑으면 되겠습니다.
그 일은 바로 keys 라는 함수가 담당!
다음에는 이제 그 key값들 (즉 소인수들) 중에서 가장 큰 것을 구하면 끝이죠. 이건 maximum 함수로!

그 세 가지를 조합하면… 답안은
maximum( keys( factor( 600851475143 )))

처럼 됩니다. 생각보다 간단하죠?

또는 함수 호출 체이닝 연산자 |> 를 써서
factor( 600851475143 ) |> keys |> maximum

흠, 눈치채셨나요? 이 |> 연산자는 UNIX shell 등에서 사용되는 pipe하고 비슷한 모양이죠.
먼저번 답안과 동작은 같지만 약간 보기가 쉬워졌달까… 뭐 사실 취향이겠지만요.
자, 이렇게 해서 맛보기로 문제 하나를 풀어봤습니다!~~

example $ julia

_

_ _ _(_)_ | A fresh approach to technical computing

(_) | (_) (_) | Documentation: http://docs.julialang.org

_ _ _| |_ __ _ | Type “?help” for help.

| | | | | | |/ _` | |

| | |_| | | | (_| | | Version 0.4.0 (2015-10-08 06:20 UTC)

_/ |__’_|_|_|__’_| | Official http://julialang.org/ release