Problem 15 : Starting in the top left corner in a 20 by 20 grid, how many routes are there to the bottom right corner (without backtracking)?

예시) 2 by 2 grid


시작점에서 끝점까지의 모든 경로는 가로 변과 세로 변으로 구성된다.
그리고, 모든 경로에서 경로의 길이는 같으며, 그 경로를 구성하는 가로 변 길이의 합과 세로 변 길이의 합은 서로 같다.
그럼, 각 점에서 오른쪽 방향(가로), 아래 방향(세로) 두 가지 방향을 선택하는 문제로 볼 수 있다. 결국, 이 문제는 정사각형이 주어졌을 때, 전체 경로 (= 가로의 경로 개수 + 세로의 경로 개수) 중에서 가로 개수와 세로 개수가 같은 경우가 몇 가지인지를 찾아내는 문제로 생각할 수 있다.

n by n 정사각형일 때 시작점에서 마지막점까지 가려면, 가로 n번, 세로 n번을 가야 한다.
따라서, 2n 개 중에서 가로 n개, 세로 n개를 선택하는 문제가 된다.

** 이 문제에 예시로 나오는 그림을 시계방향으로 45도 돌려서 보면,
파스칼의 삼각형(Pascal's triangle in wikipedia)의 한 부분이 떠오를 것이다.

n <- 20
choose(2*n, n)

프로젝트 오일러 다시 도전...
어려운 문제에 도전했다가 잘 안 풀려서, 쉬워 보이는 문제부터 풀었다.

Problem 20 : Find the sum of digits in 100!

이 문제를 푸는 알고리듬은 간단한데, R에서 문제는 자릿수가 커지면 근사치로 계산되고 유효숫자로 표현된다는 것이다.
그래서, 자릿수를 유지하면서 정확한 수치로 계산되도록 했다.
숫자를 텍스트 배열로 변환해서 푸는 방법도 있을 것 같았으나, 10진법 개념을 그대로 활용해서 풀었다.
문제를 풀고 난 후에, 다른 사람들이 공유한 코드를 보니, 간단하게 서너 줄로 작성한 다른언어 코드도 보였다.


위(위 밑줄친 부분)에서는 자릿수를 구하기 위해 log 연산의 기본 특징을 사용했는데, 일반화시키면 아래와 같다. 

비슷한 문제로 아래 16번 문제도 있었다.

Problem 16 : What is the sum of the digits of the number 21000?



아래는 Python코드다. 위의 R보다는 훨씬 편하고, 처리속도도 빠르다.

수학 / R 언어 공부와 함께 프로젝트 오일러 Start ~!

Problem 1 : Add all the natural numbers below one thousand that are multiples of 3 or 5.

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.

이 문제는 펜과 종이만 있어도 금방 풀 수 있다.


- Searching the Web, Introduction to Linear Algebra, 3/E international Edition, by Gilbert Strang -

2005년 봄...
선형대수 강의를 듣는데, 쉬어가기 페이지처럼 쓰여진 위 페이지를 보게 되었다.
SVD 응용 분야를 이야기하면서, HITS algorithm을 소개하는 내용이었다.
신기하고 재밌었다.

원래 그 전에는 국내에 위 책이 나오지 않아서, 같은 저자 Gilbert Strang 이 쓴 
<Linear Algebra and Its Applications>로 공부했었다. 그 책이 계속 교재였다면, 위 페이지는 못 봤을텐데...... -_-;;

암튼, 추가로 아래 글들을 찾아보고 HITS와 PageRank에 대해 좀 더 알아보다가, '검색'은 내 관심사 중의 하나가 되어버렸다.
- <The Use of the Linear Algebra by Web Search Engines> by Amy N. Langville and Carl D. Meyer
- <구글 페이지랭크(PageRank) 알고리듬>, 출처: 이명헌 경영스쿨
- <구글 검색 엔진의 해부학('The anatomy of large scale search engine' 번역)>, 출처: 이명헌 경영스쿨
- <Authoritative sources in a hyperlinked environment (HITS algorithm)>, 출처: 이명헌 경영스쿨
- HITS algorithm from wikipedia
- PageRank from wikipedia

당시에, <링크(Linked)>를 다시 읽고 있었는데, 그 내용과 연관되어 자꾸 관심이 커져버렸다.
과거에 컴퓨터를 처음 만져봤을 때와 인터넷을 처음 경험했을 때의 호기심이 다시 발동했다. 그러면서 드는 생각이...
'이거 미래의 우리 주위에 두루 퍼져 있을지도 모르는, Intelligent Agent 의 시작이 될 수도 있겠는걸?'

그리고, 아래 책이 나오길래 도서관에서 무작정 찾아봤다.
<Google's PageRank and Beyond : the Science of Search Engine Rankings> (Amazon.com에서 보기, Daum 책에서 보기)
구글에서 찾았던 <The Use of the Linear Algebra by Web Search Engines>의 저자들이 책으로 냈다.

도서관에 책이 들어오자마자 대출중이라, 대출 예약을 걸어두었다.
도서대출기간이 긴 사람 - 대학원생이나 교수님 - 이 빌려갔는지 좀 오래 기다려야 했다. 이 사람 대출기간도 넘겼다. -_-;;

이 책을 겨우 대출받아 보는데, 끊임없이 전개되는 행렬 연산 수식에 질려서 완독을 하지 못했다.
그냥 훑어 봐서는 완벽히 이해하기가 좀 어려웠다.
수학을 좋아하지만 잘하지는 못해서 항상 부족함을 느꼈는데, 수학공부의 중요함을 다시 한번 생각하게 됐다.
그런데, 수학공부를 계속 했느냐? 그렇지 못했다.
그 자리에서 바로 삽질을 하고 싶었지만, 워낙에 바쁜 시절인지라. -_-;;;

수학공부는 계속 되어야 한다. ㅋ
"The math learning must go on."

그 전에 읽었던 <구글스토리>라는 책도 다시 읽게 되었고,
드물게도 검색의 스타트업을 끊었던 첫눈의 시작과 끝을 보고...

몇몇 강연과 수업들. 그 때 적었던 메모들...
연습장에 쓰여진 낙서같은 아이디어들...
조금씩 찾아보던 검색서비스들...

저 페이지를 읽을 때만 해도, 현재의 ... 시작점이 될 줄은 몰랐다.
그야말로 나비효과처럼...

그 때를 생각해보니, 재미있어서 소설 한 번 써 봤다.
C'est la vie ~!

+ Recent posts