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보다는 훨씬 편하고, 처리속도도 빠르다.

  1. wizArD 2009.01.14 23:02

    블로그 다시 시작했냐. 수학은 왜 공부해? 알고리즘 만들어?

    • unknown linker 2009.01.16 10:48 신고

      블로그는 자주는 아니더라도, 꾸준히 계속 하려고요.
      수학공부는 요즘 머리가 굳는 것 같아서... -_-;;

수학 / 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.

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


  1. ㅁㅁ 2008.11.04 03:04

    1번풀고 중단하신 건지요...

+ Recent posts